相同的树

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

题目

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

分析

先比较根节点是否相同，如果不相同则直接返回false,如果相同则分别比较左右子树。如果两个数不相同的话，有可能在比较的过程，一个存在子树，而另一个则不存在子树，此时无法再比较根节点。所以有一个出现为空，而另一个不为空的情况下，则证明这两个树也是不相同的树。

答案

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

因为是以根节点出发，从上往下去对比下去，这种方法被称为深度优先算法。与之对应的还有广度优先算法，时间复杂度和空间复杂度和深度优先算法差不多。所谓广度优先算法，就不光比较两个根节点的值是否相同了，还要比较他的左右子树的结构是否相同，如果左右子树的结构不同，则也认为不是相同的树。

如果左右子树的结构相同则将非空节点加入两个队列。如果左子树不为空，则优先加入左子树。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        }
        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
        Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
        queue1.offer(p);
        queue2.offer(q);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            if (node1.val != node2.val) {
                return false;
            }
            TreeNode left1 = node1.left, right1 = node1.right, left2 = node2.left, right2 = node2.right;
            if (left1 == null ^ left2 == null) {
                return false;
            }
            if (right1 == null ^ right2 == null) {
                return false;
            }
            if (left1 != null) {
                queue1.offer(left1);
            }
            if (right1 != null) {
                queue1.offer(right1);
            }
            if (left2 != null) {
                queue2.offer(left2);
            }
            if (right2 != null) {
                queue2.offer(right2);
            }
        }
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

复杂度

• 时间复杂度: O(min(m,n))，如果两个树相同，则需要遍历整个树。如果不相同，谁先为空，则停止遍历。
• 空间复杂度：O(min(m,n))，因为这里使用了递归，所以这里主要就是递归占用的栈空间。

总结

广度遍历相对与深度遍历，稍微有点复杂，也不便理解。没有广度遍历直观。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！