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(logn)

代码

public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {//p或者q只有一方是null
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

Subtree

You have two every large binary trees: T1, with millions of nodes, and
T2, with hundreds of nodes. Create an algorithm to decide if T2 is a
subtree of T1.

递归解法

思路:

递归退出条件是T1或者T2是空, 如果T2是空那么T2是T1的子树, 返回true 如果T1是空 返回false.
递归的条件是T2和T1是same tree 或者T2是T1的子树的subtree

代码

public boolean isSubtree(TreeNode T1, TreeNode T2) {
        if (T2 == null) {
            return true;
        }
        if (T1 == null) {
            return false;
        }
        return isSame(T1, T2) || isSubtree(T1.left, T2) || isSubtree(T1.right, T2);
    }

Symmetric Tree

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

递归解法

思路

与sametree思路相同, 不过递归条件是左子树与右子树想对比

复杂度

时间O(n) 空间栈O(logn)

代码

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