101.对称二叉树.md

101. 对称二叉树

url

题目

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

例如，二叉树 [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

方法

可递归，可遍历

对称的树，三个结束条件

• 如果p和q都不为空，则为true，毕竟对称的树，节点数量和方向都得一样吧？
• 如果p和q其中一个为空，则为false，说明节点数量或者方向不对呀？
• 如果p和q的值不相等的话，直接false
• 和相同树不一样的是递归p的左节点和q的右节点，p的右节点和q的右节点

code

js

let isSymmertric = root => {
    let isSym = (p, q) => {
        if (p === null && q === null) return true;
        if (p === null || q === null) return false;
        if (p.val !== q.val) return false;
        return isSym(p.left, q.right) && isSym(p.right, q.left);
    }

    if (root === null) return true;
    return isSym(root.left, root.right)
}

go

func isSymmetric(root *TreeNode) bool {
	var isSymmetric1 func (t1, t2 *TreeNode) bool
	isSymmetric1 = func (t1, t2 *TreeNode) bool {
		if t1 == nil && t2 == nil {
		return true
	}
		if t1 == nil || t2 == nil {
		return false
	}
		if t1.Val != t2.Val {
		return false
	}
		return isSymmetric1(t1.Left, t2.Right) && isSymmetric1(t1.Right, t2.Left)
	}
	if root == nil {
		return true
	}
	return isSymmetric1(root.Left, root.Right)
}

java

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