Same Tree

#algorithms #csharp #leetcode #easy

#100.Same Tree

Problem statement

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2

Input: p = [1,2], q = [1,null,2]
Output: false

Explanation

給定兩個二元樹的樹根 p 和 q ，檢查兩個二元樹是否相同，相同的定義為結構相同、節點也具有相同的值，最終返回 true 或 false

Solution

有關二元樹的題目，解法通常離不開遞迴，這題要比較兩個二元樹結構是否完全相同，用遞迴可寫出優雅的解法，一開始先判斷二元樹是否為 null，若其中一個是 null，返回兩者是否相等的判斷結果，若兩個節點都不是 null，則比較兩者節點值是否相同，若不同則在最底部返回 false，若節點值相同則繼續走訪左子樹和右子樹，呼叫自己 IsSameTree 並傳入要比較的對應節點，直到判斷完成

public bool IsSameTree(TreeNode p, TreeNode q)
{
    if (p == null || q == null) return p == q;

    if (p.val == q.val)
        return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);

    return false;
}