100. Same Tree

Given two binary trees, 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:
   1   1
   / \  / \
  2 3 2 3
Output: true

Example 2:

Input:
 1   1
   /      \
  2    2
Output: false

题目

判断两棵二叉树是否相等

思路

二叉树题目一般都需要递归，这也是由于二叉树本身就是递归结构。
递归三步走：

1. 终止条件（也可理解为最小样本情况）
2. 自己调用自己
3. 处理返回值

回到题目本身：

1. 终止条件：当两个节点其中一个为空，或值不相等时，返回false;当两个节点都为空时，返回true；当两个节点不为空且值相等时，继续往下找；
2. 所以递归也就形成了，就是判断两棵树的左右孩子是否相同，自己调自己，分别传入左右孩子；
3. 返回值，那就是（左孩子是否相等&右孩子是否相等）

所以有代码如下：

代码

public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        boolean sameOrNotLeft = isSameTree(p.left, q.left);
        boolean sameOrNotright = isSameTree(p.right, q.right);

        return sameOrNotLeft && sameOrNotright;
    }