第6题 力扣LeetCode 热题 HOT 100(101. 对称二叉树)_力扣hot100有哪些

第6题 力扣LeetCode 热题 HOT 100(101. 对称二叉树)

题目

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

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

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

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

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

题解

有两种解法，迭代和递归。

递归解法，以根节点的左右子树为线索，开始往下走，往下走的过程左右子树中满足对称，两颗树对称的条件为，父节点值相同，同时树A的左子树与树B的右子树对称，树A的右子树与树B的左子树对称。

let checkTree = function(leftNode, rightNode){
    //树A与树B的两个节点都为空，那么树A与树B（左孩子或者右孩子）满足对称条件。
    if(!leftNode && !rightNode) return true;
    else if((!leftNode && rightNode) ||(leftNode && !rightNode)  ) return false;
    if(leftNode.val!=rightNode.val) return false;
    else{
        //只有一颗树的左右孩子都满足对称，这棵树才满足对称
        return checkTree(leftNode.left, rightNode.right)&& checkTree(leftNode.right, rightNode.left);
    }

}
var isSymmetric = function(root) {
    if(!root ) return true;
    else{
        return checkTree(root.left, root.right);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17