题目描述
请实现一个函数，用来判断一棵二叉树是不是对称的。
如果一棵二叉树和它的镜像一样，那么它是对称的。
数据范围
树中节点数量 [0,100]。
样例
如下图所示二叉树[1,2,2,3,4,4,3,null,null,null,null,null,null,null,null]为对称二叉树： 1 / \ 2 2 / \ / \ 3 4 4 3 如下图所示二叉树[1,2,2,null,4,4,3,null,null,null,null,null,null]不是对称二叉树： 1 / \ 2 2 \ / \ 4 4 3
方法一：二叉树+递归 O(n)
如果两个子树互为镜像，则满足以下条件：
- 两子树的根结点的值相同。
- 第一课子树的左子树和第二课子树的右子树互为镜像，第一课子树的右子树和第二课子树的左子树互为镜像。
我们拿题目样例来举例，看看具体是如何实现的：
第一步： 判断根结点是否为空，如果不为空，递归判断子树是否对称。
第二步： 判断根结点的左右结点是否相等， 如果相等再往左右子树去递归。
第三步： 继续往左右子树判断结点是否相等。
第四步： 发现都满足条件，所以该树是对称的，返回 true 即可。
/** * 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) { //根结点为空或子树对称都满足题目条件 return !root || dfs(root->left, root->right); } bool dfs(TreeNode* p, TreeNode* q) { //不能存在p和q只有一个为空的情况，要么都不空要么都为空 if (!p || !q) return !p && !q; //当前结点值相等，并且左右子树也满足要求 return p->val == q->val && dfs(p->right, q->left) && dfs(p->left, q->right); } };
方法二：迭代 O(n)
我们可以用栈模拟递归，对左子树进行中序遍历，对右子树进行反中序遍历，只有在遍历每个结点是两者值相同，两子树才互为镜像。
我们还是拿题目的样例来举例，看一看具体的实现过程：
第一步： 先将根结点的左右孩子分别推入 left 和 right 的栈中。
第二步： 从 lc 一直向左，将沿路上的所有结点都推入 left 栈中。因为模拟的是中序遍历，所以访问顺序是左结点 -> 根结点 -> 右结点。而题目是要判断该树是否对称，所以我们对根结点右子树进行反中序遍历，即访问顺序是右结点 -> 根结点 -> 左结点，故从 rc 一直向右，将沿路上的所有结点都推入 right 栈中。
第三步： 完成第二步之后，就可以分别弹出 left 和 right 的栈顶元素 tl 和 tr ，然后判断是否相等，并且如果 tl 有右孩子就往右孩子走，tr 有左孩子就往左孩子走。
第四步： 很显然，左边结点 3 没有右孩子且右边结点 3 没有左孩子，所以继续弹出栈顶元素进行比较。
第五步： 发现栈顶元素相同，判断左边的结点是否有右孩子且右边的结点是否有左孩子，发现还存在结点 4 ，故往结点 4 方向走。
第六步： 对结点 4 进行第二步操作，发现只有它自己了，所以继续执行栈的弹出操作。发现弹出元素相等，并且没有其左右孩子，栈为空结束循环操作，返回结果 true 。
/** * 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 (!root) return true; stack<TreeNode*>left, right; TreeNode* lc = root->left; TreeNode* rc = root->right; while (lc || rc || left.size()) { //模拟中序遍历和反中序遍历，先遍历左子树和右子树 while (lc && rc) { left.push(lc), right.push(rc); lc = lc->left, rc = rc->right; } //指针不能一个为空，一个不为空 if (lc || rc) return false; //弹出栈顶元素，进行比较 lc = left.top(), rc = right.top(); left.pop(), right.pop(); if (lc->val != rc->val) return false; //往弹出的元素的右子树和左子树继续遍历 lc = lc->right, rc = rc->left; } return true; } };
欢迎大家在评论区交流~
