LeetCode 100. Same Tree

题目:100. Same Tree

解法一 Recursion

思路

两树相同,则比较的两个节点中不能有其中一个为 null,节点的值需要相等,两个节点的左子树和右子树也要相等。

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

        return isSameTree(q.left, p.left) && isSameTree(q.right, p.right);
    }
}
复杂度分析
  • 时间复杂度
    • 遍历一遍二叉树,花费 O(n) 时间
  • 空间复杂度
    • O(n) – Skewed Tree
    • O(logn) – Balanced Tree

解法二 Iteration

思路

和递归思路相同,就是使用了 queue 储存两个树将要比较的节点。(用 stack 也可以)

代码
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(p);
        queue.offer(q);

        while (!queue.isEmpty()) {
            TreeNode ptree = queue.poll();
            TreeNode qtree = queue.poll();
            if (ptree == null && qtree == null) continue; // 当两树都是空树时,继续循环
            else if (ptree == null || qtree == null) return false;
            else if (ptree.val != qtree.val) return fasle;
            else {
                queue.offer(p.left);
                queue.offer(q.left);
                queue.offer(p.right);
                queue.offer(q.right);
            }
        }
        return true;
    }
}
复杂度分析
  • 时间复杂度
    • O(N)
  • 空间复杂度
    • O(N) Keep the queue
Takeaway

第101题 symmetric tree 思路相同,p,q树都是 root,然后左子树和右子树比,右子树和左子树比。recursion时需要满足根节点相等且左右对称。

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!