网络异常，图片无法展示
|
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [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 复制代码
进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
解题思路
递归解题
var isSymmetric = function(root) { function check(a,b){ // 如果当前两节点都为null，符合对称要求 if(a===null && b===null) return true; // 如果某一个节点为空或者两节点值不同，不符合对称要求 if(a===null || b===null || (a.val!==b.val)) return false; // 递归校验子树 return check(a.left,b.right)&&check(a.right,b.left) } return check(root.left,root.right) }; 复制代码
迭代方式
首先我们来看一下前序遍历的过程：
网络异常，图片无法展示
|
可以看到，如果当前节点有左子树，会优先处理左子树，直到叶子节点位置，然后会处理与之对应的右子树。
如果右子树有左子树，依然优先处理左子树，然后处理与之对应的右子树。
然后继续向上回溯处理父节点的右子树，直到回溯到根节点，处理根节点的右子树。
所以，我们可以从根节点开始迭代，将根节点的值放入到结果数组中，然后将根节点入栈，然后向下处理当前节点的左子树，直到叶子节点位置。
此时，栈顶保存的就是当前叶子节点，将栈顶元素弹出，当前节点更新为栈顶元素的右子树，因为该节点为叶子节点，所以右子树为空，此时继续弹出栈顶元素，此时栈顶元素为叶子节点的父节点，将当前元素更新为它的右子树。
右子树处理到最后依然会来到叶子节点，此时栈顶元素为该叶子节点，弹出该节点，因为该节点为叶子节点，所以右子树为空，继续弹出栈顶元素，则继续向上回溯。
整个遍历过程一直重复这样的过程，直到处理完整棵二叉树的最右侧节点，此时栈为空且当前节点为空，结束循环，完成二叉树的前序遍历。
动画演示
网络异常，图片无法展示
|
迭代解题
基于以上二叉树迭代过程的演示，结合本题中我们对对称二叉树性质的理解，本题可以利用如下方式迭代解题。
利用迭代的方式遍历左子树和右子树,
左子树采用根左右的顺序，右子树采用根右左的顺序,
如果两棵子树对称，则左子树根左右方式遍历与右子树根右左方式遍历结果应该是相同的。
var isSymmetric = function(root) { // 利用迭代的方式遍历左子树和右子树 // 左子树 根左右顺序 右子树 根右左顺序 // 如果两棵子树对称，则左子树根左右方式遍历与右子树根右左方式遍历结果相同 const stack1 = [],stack2 = []; let a = root.left,b = root.right; while(a||stack1.length){ while(a){ if(b===null || (a.val!==b.val)) return false; stack1.push(a); stack2.push(b); a = a.left; b = b.right; } if(b) return false; a = stack1.pop().right; b = stack2.pop().left; } return b===null; }; 复制代码
至此我们就完成了 leetcode-101-对称二叉树
如有任何问题或建议，欢迎留言讨论！
