101. 对称二叉树
101. 对称二叉树
力扣题目链接[1]
给你一个二叉树的根节点 root，检查它是否轴对称。
示例1：
输入：root = [1,2,2,3,4,4,3]
输出：true
「提示：」
- 树中节点数目在范围
[1, 1000]内 100 <= Node.val <= 100
进阶：你可以运用递归和迭代两种方法解决这个问题吗？
思路：
首先使用递归来求解。
递归
首先来看递归终止条件。当前节点的左右子节点都是空，那么当前节点就是对称的，直接返回true。如果当前节点只有左子节点或者右子节点，或者子节点的值不相等，那就是不对称的，直接返回false。
然后继续递归处理左左右右和左右右左。直至判断完整个二叉树，亦或者不对称提前返回。
/**
* @param {TreeNode} root
* @return {boolean}
*/
const recur = (left, right) => {
if (left === null && right === null) return true;
if (left === null || right === null || left.val !== right.val) return false;
return recur(left.left, right.right) && recur(left.right, right.left);
}
var isSymmetric = function(root) {
return root === null || recur(root.left, root.right);
};
迭代
递归的根本是通过调用栈实现，那么这里可以使用辅助栈来题解。
如果根节点不存在，那么二叉树本身就是对称的。如果根节点不为空，那么将左右子节点同时入栈，方便后续判断。
在循环中，同时弹出左右子节点。
如果左右子节点都存在，则进一步判断值是否相等，如果不相等就意味着不对称，提前返回false。如果相等则继续判断子节点是否对称。做法就是将左左、右右、右左、左右放入栈中，方便下次弹出判断。放入的顺序刚好是左在前，右在后，弹出刚好相反。
如果左节点或者右节点不存在，则意味着不相等，提前返回false。
如果遍历完二叉树都没有提前返回，则意味着二叉树对称，返回true。
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
if (!root) return true;
let stack = [root.left, root.right];
while(stack.length) {
let right = stack.pop();
let left = stack.pop();
if (left && right) {
if (left.val !== right.val) return false;
stack.push(left.left, right.right, right.left, left.right);
} else if (left || right) return false;
}
return true;
};
总结
本题分别采用递归和迭代来实现对称二叉树的判断。递归需要注意递归的终止条件，迭代需要注意使用栈来存放节点的顺序。
参考资料
[1]
力扣题目链接: https://leetcode-cn.com/problems/symmetric-tree/
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2022-04-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
