《代码随想录》--二叉树（二）

101.对称二叉树

leetcode链接

代码实现

• 递归

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return compare(root.left,root.right);
    }
    public boolean compare(TreeNode left,TreeNode right){
        if(left == null && right == null) return true;
        else if(left != null && right == null) return false;
        else if(left == null && right != null) return false;
        else if(left.val != right.val) return false;

        boolean out = compare(left.left,right.right);
        boolean in = compare(left.right,right.left);
        return out && in;
    }
}

• 迭代

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while(!queue.isEmpty()){
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            if(left == null && right == null) continue;
            if(left == null || right == null || left.val != right.val) return false;

            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;
    }
}

分析

• 递归法
  • 传入左节点和右节点
  • 判断一下他们的值是否为空，是否相等
  • 再传入外侧的节点，然后传入内侧的节点
  • 内外都对称才能返回true
• 迭代法
  • 使用队列来存储两个节点
  • 每个节点成对加入成对取出比较

相关题目

相同的树

代码

• 递归

class Solution {
    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 != 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;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(p);
        queue.offer(q);
        while(!queue.isEmpty()){
            p = queue.poll();
            q = queue.poll();
            if(p == null && q == null) continue;
            if(p == null || q == null || p.val != q.val) return false;

            queue.offer(p.left);
            queue.offer(q.left);
            queue.offer(p.right);
            queue.offer(q.right);
        }
        return true;
    }
}

另一棵树的子树

代码

• 双递归

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null && subRoot == null) return true;
        else if(root == null || subRoot == null) return false;
        else return isSameTree(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }
    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);
    }
}

) return false;
else return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}