You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

101. 对称二叉树 - Symmetric Tree

. 1 min read

101. 对称二叉树 - Symmetric Tree

[Level Tranversal]

给定一个二叉树,检查它是否是镜像对称的。

Example:

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

solution

My solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirrorTree(root, root);
    }
    
    public boolean isMirrorTree(TreeNode left, TreeNode right) {
        if(left == null)
            return right == null;
        if(right == null)
            return left == null;
        if(left.val == right.val)
            return isMirrorTree(left.left, right.right) && isMirrorTree(left.right, right.left);
        return false;
    }
}

复杂度分析 16ms O(|V|)

Other Solution

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root ==null)
            return true;
        return traversal(root.left,root.right);
    }
    public boolean traversal(TreeNode l,TreeNode r){
        if(l ==null || r==null)
            return l==r;
        if(l.val != r.val)
            return false;
        boolean ret= traversal(l.left,r.right) && traversal(l.right,r.left);
        return ret;
    }
    
}

复杂度分析 O(|V|) 7ms

该方法首先判断了 false 的情况,跳过了许多无效递归。

Notes