leetcode: Symmetric Tree

问题描述：

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

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

 

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

 

 

Note:
Bonus points if you could solve it both recursively and iteratively.

原问题链接：https://leetcode.com/problems/symmetric-tree/

 

问题分析

　　这个问题相对来说还是比较简单的，这里针对两种解决方法讨论一下。

 

递归法

　　因为这里要判断一棵树是不是对称二叉树，所以它就有一个可以递归推导的属性。对于一个单独的根节点来说，如果它的左右子树都是空，说明它是对称的。如果它本身就是空的，那也是对称的。那么对于它同时有左右子树的情况呢？这里有一个更细节的地方，假设它有左右子树。那么它的对称属性要成立的话，必然要求它的左右子树的根节点相等，同时左子树的右子树要和右子树的左子树递归的相等。

　　按照这个递归的特性，我们可以得到如下的代码：

 

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

 

迭代法

　　如果我们仔细观察的话，会发现对称二叉树还有一个有趣的特性可以利用。就是如果我们按照中序遍历的方式去遍历整个树，并将遍历过的元素记录下来的话。这个元素构成的访问序列必然是对称的。所以我们可以根据中序遍历后得到的结果去判断它是否对称来求得结果。

　　因为按照这个思路的实现相对比较简单，这里就不再详细赘述了。其实除了这种迭代法以外，还有一种稍微有一点变化的实现。这种方式比较有特点，在这里特别说明一下。就是在得到一棵树的根节点的左右两个子节点之后，我们对左右两棵子树分别进行层次序的遍历，只是左子树是从左到右的遍历，而右子树是从右到左的遍历。每次遍历的时候就将元素的子节点往队列里加。在每次从队列里取元素的时候则判断两边是否相等。这种方法也是间接利用了对称二叉树的特性。

　　详细的实现如下：

 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        Queue<TreeNode> q1 = new LinkedList<TreeNode>();
        Queue<TreeNode> q2 = new LinkedList<TreeNode>();
        q1.add(root.left);
        q2.add(root.right);
        while(!q1.isEmpty() && !q2.isEmpty()) {
            TreeNode left = q1.remove();
            TreeNode right = q2.remove();
            if(left == null && right == null) continue;
            if(left == null || right == null) return false;
            if(left.val != right.val) return false;
            q1.add(left.left);
            q1.add(left.right);
            q2.add(right.right);
            q2.add(right.left);
        }
        return true;
    }
}