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.

递归法

复杂度

时间 O(N) 空间 O(h) 递归栈空间

思路

如果两个根节点一个为空，一个不为空，或者两个根节点值不同，说明出现了不一样的地方，返回假。如果两个节点都是空，则是一样的，返回真。然后我们再递归它们的左右节点，如果递归结果中一个或两个是假，就返回假。否则，说明左右子树都是完全一样的。

代码

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

Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1   / \  2   2 / \ / \3  4 4  3

But the following is not:

    1   / \  2   2   \   \   3    3

递归法

复杂度

时间 O(N) 空间 O(h) 递归栈空间

思路

唯一不同于Same Tree，对称树是要判断左节点的左节点和右节点的右节点相同（外侧），左节点的右节点和右节点的左节点相同（内测）。

代码

public class Solution {

public boolean isSymmetric(TreeNode root) {    return root == null ? true : helper(root.left, root.right);}private boolean helper(TreeNode node1, TreeNode node2){    if(node1 == null && node2 == null){        return true;    }    if(node1 == null || node2 == null || node1.val != node2.val){        return false;    }    return helper(node1.left, node2.right) && helper(node1.right, node2.left);}

}