( “树” 之 DFS) 101. 对称二叉树 ——【Leetcode每日一题】

101. 对称二叉树

给你一个二叉树的根节点 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

进阶： 你可以运用递归和迭代两种方法解决这个问题吗？

思路：递归

递归结束条件：

• 都为空指针则返回 true；
• 只有一个为空或者对应节点值不相等，则返回 false。

递归过程：

• 判断 A 的右子树与 B 的左子树是否对称；
• 判断 A 的左子树与 B 的右子树是否对称；
• 只有都相等时，才返回true。

代码：(Java、C++)

Java

/* Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {return dfs(root.left, root.right);}public boolean dfs(TreeNode l_root, TreeNode r_root){if(l_root == null && r_root == null) return true;if(l_root == null || r_root == null || l_root.val != r_root.val){return false;}return dfs(l_root.left, r_root.right) && dfs(l_root.right, r_root.left);}
}

C++

/* Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isSymmetric(TreeNode* root) {return dfs(root->left, root->right);}bool dfs(TreeNode* l_root, TreeNode* r_root){if(l_root == NULL && r_root == NULL) return true;if(l_root == NULL || r_root == NULL || l_root->val != r_root->val){return false;}return dfs(l_root->left, r_root->right) && dfs(l_root->right, r_root->left);}
};

运行结果：

复杂度分析：

• 时间复杂度：$O(n)$，n为节点数，这里遍历了整棵树。
• 空间复杂度：$O(n)$，这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n。

题目来源：力扣。

放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我 leetCode专栏，每日更新！

注： 如有不足，欢迎指正！