---

题目描述

【leetcode】101. 对称二叉树( Symmetric Tree )

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

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

说明:
如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

第一次解答

思路
官方题解的分析角度不好理解，这里是另一种角度。本题考察的不是递归也不是非递归，考察的是在你知道了前序遍历的基础上，如何灵活的修改前序遍历的代码去镜像对称地遍历二叉树。
要判判断二叉树是不是对称的，只需要访问镜像元素值是否相等。
那么如何访问镜像元素呢？对左右子树做相反顺序的遍历即可。
那么怎么对左右子树做相反顺序的遍历呢？A节点的左子树进行前序遍历【DLR，即当前结点, 左孩子, 右孩子】，同时，对A节点的右子树进行【DRL，即当前结点, 右孩子, 左孩子】遍历。
可以在前序遍历的基础上修改。修改为一次同时遍历2个结点。
首先遍历左右子树的当前节点，然后对于左子树采用DLR方式遍历的同时，对于右子树采用DRL方式遍历，这样同时访问的两个结点是镜像位置的两个结点，若结点值不同，则不对称。
这里采用递归实现。

test case:
[]
[1,2,2,3,4,4,3]

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(nullptr == root)
            return true;
        return isMirror(root->left, root->right);
    }
    bool isMirror(TreeNode *tl, TreeNode *tr){
        // 访问D结点
        if(nullptr == tl && nullptr == tr)
            return true;
        if(nullptr == tl || nullptr == tr)
            return false;
        if(tl->val == tr->val){
            // 访问L, R孩子
            return isMirror(tl->left, tr->right) && isMirror(tl->right, tr->left);
        }
        return false;
    }
};

结果：

相关/参考链接