100. Same Tree

解法一

思路

直观地判断是否是相同的树：如果两个树的同位置节点不相等，返回false。如果两者有一个为 Null，返回 false。如果都为 null, 返回 true。

代码

class Solution {
    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;
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

复杂度分析

• 时间复杂度 O(N) 每个节点都会经过
• 空间复杂度
  • 最好情况 O(logN) 完全平衡二叉树
  • 最坏情况 O(N) 所有数都在 left subtree

解法二

思路

通过入队出队操作，将两个树的同位置元素进行比较。

代码

class Solution {
        public boolean isSameTree(TreeNode p, TreeNode q) {
                LinkedList<TreeNode> queue = new LinkedList<>();

                queue.add(p);
                queue.add(q);

                while (!queue.isEmpty()) {
                        TreeNode ptree = queue.poll();
                        TreeNode qtree = queue.poll();
                        if (ptree == null && qtree == null) continue;
                        if (ptree == null || qtree == null || ptree.val != qtree.val) return false;
                        queue.add(ptree.left);
                        queue.add(qtree.left);
                        queue.add(ptree.right);
                        queue.add(qtree.right);
                }
                return true;
        }
}

复杂度分析

• 时间复杂度 O(N)
• 空间复杂度 O(N) (因为会把所有元素储存在里面？)

Takeaway

• 先序遍历，中序遍历，后序遍历

本作品采用《CC 协议》，转载必须注明作者和本文链接