LeetCode 100. Same Tree

題目

Given two binary trees, write a function to check if they are equal or not.

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

翻譯

給定兩個二元樹，判斷這兩個樹的每一個節點中的值與節點位置是否都相同

思路

這題跟LeetCode 226. Invert Binary Tree很像，用遞迴解會比迴圈容易理解很多。

比較兩個節點的值(val)，如果val不同或是子節點數量不相同，都是false，子節點不同就是說其中一邊有左右節點，另外一邊就只有一個左節點或右節點這種情況。 當目前val與子節點數量都相同，再比較子節點是否相同，將子節點丟入判斷是否相同的function，直到比較完毎個節點都是一樣的，結果才會是true。

解題

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    // 如果兩個node都是null，代表所有node比較都是一樣的
    if(p === null && q=== null){
        return true;
    }

    // one null, other is not null, false
    if(p !== null && q=== null || p === null && q !== null){
        return false;
    }

    // val diff, false
    if(p.val != q.val){
        return false;
    }
    // find next level of tree
    return isSameTree(p.right,q.right)&&isSameTree(p.left, q.left);
};

以treeA[1,2,0,3,4,null,5]與treeB[1,2,0,3,4,5,5]兩個二元樹為例

• treeA與treeB第一個節點的val均為1，也都有兩個子節點，進行子節點的比較
• 比較treeA 下一層的左節點2與 treeB 下一層的左節點2，兩者val相同
• 再向下比較，會發現treeA，treeB在左節點下的[3,4]也都是相同的
• 接著比較treeA 下一層的右節點0與 treeB 下一層的右節點0
• treeA節點0下一層的左節點為null，右節點為5，treeB節點0下一層的左節點則是5
• 以上可以判斷這兩個tree是不相等的