101. 对称二叉树

Posted on Edited on In , ,
转载自Leet Code

题目描述

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

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

进阶： 你可以运用递归和迭代两种方法解决这个问题吗？

我的代码：迭代

\(T(N) = O(N)\), \(S(N) = O(N)\)

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class MySolution101 // 前序遍历
{
    public boolean isSymmetric(TreeNode root) 
    {
    	TreeNode p = root; TreeNode q = root;
    	Stack<TreeNode> stackPre = new Stack();
    	Stack<TreeNode> stackPos = new Stack();
    	
    	while (true)
    	{
    		if (p!=null&&q!=null)
    		{
    			if (p.val!=q.val) return false;
    			stackPre.push(p); stackPos.push(q);
    			p = p.left; q = q.right;
    		}
    		else if ((p==null&&q!=null)||(p!=null&&q==null)) return false;
    		else if (!stackPre.isEmpty()&&!stackPos.isEmpty())
    		{
    			p = stackPre.pop().right;
    			q = stackPos.pop().left;
    		}
    		else if (stackPre.size()!=stackPos.size()) return false;
    		else return true;
    	}
    }
}

我的代码：递归

\(T(N) = O(N)\), \(S(N) = O(N)\)

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class MySolution101 
{
    public boolean isSymmetric(TreeNode root) 
    {
        if (root==null) return true;
    	return PreOrder(root.left,root.right);
    }
    
    public boolean PreOrder (TreeNode p, TreeNode q)
    {
    	if (p==null&&q==null) return true;
    	else if (p==null||q==null) return false;
    	
    	if (p.val!=q.val) return false;
    	else return PreOrder(p.left, q.right)&&PreOrder(p.right, q.left);
    }
}

方法一: 递归

\(T(N) = O(N)\), \(S(N) = O(N)\)

如果一个树的左子树和右子树镜像对称，那么这个树是对称的。

因此，该问题可以转化为：两棵树什么时候互为镜像？ - 它们的两个根节点具有相同的值； - 每棵树的右子树都与另一棵树的左子树镜像对称；

我们可以实现这样的一个递归函数，通过同步移动两个指针的方法来遍历这棵树。 指针 p 和指针 q 一开始都指向树根，然后 p 右移时 q 左移、 p 左移时 q 右移。 每次检查当前 p 和 q 的值是否相等，若相等则再判断左右子树是否对称。

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution101 
{
    public boolean isSymmetric(TreeNode root) 
	{
        return check(root, root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) 
            return true;

        if (p == null || q == null) 
            return false;

        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }
}

方法二: 迭代

\(T(N) = O(N)\), \(S(N) = O(N)\)

引入队列来将递归程序改为迭代程序。 队列中每两个连续的节点的值应该相等，且子树互为镜像。

初始化时将根节点入队两次。 之后每次提取两个节点并且比较它们的值，并将两个节点的左右子节点按照相反顺序插入队列。 当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续节点）时，结束算法。

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution101 
{
    public boolean isSymmetric(TreeNode root) 
	{
        return check(root, root);
    }

    public boolean check(TreeNode u, TreeNode v) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(u);
        q.offer(v);
        while (!q.isEmpty()) 
		{
            u = q.poll();
            v = q.poll();
            if (u == null && v == null) 
                continue;
            if ((u == null || v == null) || (u.val != v.val)) 
                return false;

            q.offer(u.left);
            q.offer(v.right);

            q.offer(u.right);
            q.offer(v.left);
        }
        return true;
    }
}