100md.md

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是不相等的