101. 对称二叉树【同时遍历两棵树】【C++】
题目描述
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
提示：
树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100
思路
对于二叉树的题目，首先分析使用什么遍历顺序，我们需要比较左子树外侧(root->left)和右子树外侧(root->right)，左子树内侧(root->right)和右子树内侧(root->left)，它们都相等时才满足。我们需要后序遍历，因为需要从下到上传递是不是对称二叉树的信息。
代码
class Solution {
public:bool isSymmetric(TreeNode* root) {if (root == nullptr) {return true;}return dfs(root -> left, root -> right);}bool dfs(TreeNode* left, TreeNode* right) {if (left && right == nullptr) { //终止条件return false;} else if (left == nullptr && right){return false;} else if (left == nullptr && right == nullptr) {return true;} else if (left -> val != right -> val) {return false;}bool sameOut = dfs(left -> left, right -> right); //后序遍历，向上传递信息bool sameIn = dfs(left -> right, right -> left);return sameIn && sameOut;}
};
总结
后序遍历：一般是从叶子节点返回信息，所以有这个特性就可以考虑后序遍历。