LeetCode·101.对称二叉树·递归
链接:https://leetcode.cn/problems/symmetric-tree/solution/by-xun-ge-v-4ngq/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
题目![](https://img-blog.csdnimg.cn/523b66ecfacb4f87826b8fc3b0386772.png)
示例![](https://img-blog.csdnimg.cn/202914d91c074f8eaf489225e547a099.png)
思路
解题思路
递归
递归三部曲
- 确定递归函数的参数和返回值
因为我们要比较的是根节点的两个子树是否是相互翻转的,进而判断这个树是不是对称树,所以要比较的是两个树,参数自然也是左子树节点和右子树节点。
返回值自然是bool类型。
代码如下:
bool dfs(struct TreeNode* left , struct TreeNode* right)
- 确定终止条件
要比较两个节点数值相不相同,首先要把两个节点为空的情况弄清楚!否则后面比较数值的时候就会操作空指针了。
节点为空的情况有:(注意我们比较的其实不是左孩子和右孩子,所以如下我称之为左节点右节点)
- 左节点为空,右节点不为空,不对称,return false
- 左不为空,右为空,不对称 return false
- 左右都为空,对称,返回true
此时已经排除掉了节点为空的情况,那么剩下的就是左右节点不为空:
- 左右都不为空,比较节点数值,不相同就return false
此时左右节点不为空,且数值也不相同的情况我们也处理了。
代码如下:
if(left == NULL && right == NULL){
return true;
}else if(left == NULL || right == NULL)
{
return false;
}else if(left->val != right->val)
{
return false;
}
注意上面最后一种情况,我没有使用else,而是elseif, 因为我们把以上情况都排除之后,剩下的就是 左右节点都不为空,且数值相同的情况。
- 确定单层递归的逻辑
此时才进入单层递归的逻辑,单层递归的逻辑就是处理 右节点都不为空,且数值相同的情况。
- 比较二叉树外侧是否对称:传入的是左节点的左孩子,右节点的右孩子。
- 比较内测是否对称,传入左节点的右孩子,右节点的左孩子。
- 如果左右都对称就返回true ,有一侧不对称就返回false 。
代码如下:
dfs(left->left , right->right) && dfs(left->right , right->left)
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/*
*dfs:判断两个节点是否相等
struct TreeNode* left:树节点
struct TreeNode* right:树节点
返回值:相等返回true;不相等返回false
*/
bool dfs(struct TreeNode* left , struct TreeNode* right)
{
if(left == NULL && right == NULL)
{
return true;
}else if(left == NULL || right == NULL)
{
return false;
}else if(left->val != right->val)
{
return false;
}
return dfs(left->left , right->right) && dfs(left->right , right->left);
}
/*
*isSymmetric:判断一个树是不是对称
struct TreeNode* root:根节点
返回值:对称返回true;不对称返回false
*/
bool isSymmetric(struct TreeNode* root)
{
if(root == NULL)
{
return true;
}
return dfs(root->left,root->right);
}
作者:xun-ge-v
链接:https://leetcode.cn/problems/symmetric-tree/solution/by-xun-ge-v-4ngq/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相关文章
- 【LeetCode】完全二叉树的节点个数 [M](递归)
- 【LeetCode】将N叉树编码为二叉树(使用深度优先递归)
- [LeetCode] Combinations
- LeetCode_二叉平衡树_简单_110.平衡二叉树
- LeetCode_动态规划_中等_97.交错字符串
- LeetCode_动态规划_中等_264.丑数 II
- LeetCode_回溯_中等_90.子集II
- LeetCode_二叉树_简单_501.二叉搜索树中的众数
- LeetCode_二叉树_中等_236.二叉树的最近公共祖先
- LeetCode_动态规划_递归_二叉树_中等_337.打家劫舍 III
- LeetCode·每日一题·1145.二叉树着色游戏·贪心
- LeetCode·每日一题·1768.交替合并字符串·模拟
- LeetCode·二叉树前序、中序、后序遍历·递归
- LeetCode --- 57. Insert Interval
- [LeetCode] 106. Construct Binary Tree from Inorder and Postorder Traversal 由中序和后序遍历建立二叉树
- [LeetCode] 362. Design Hit Counter 设计点击计数器
- [LeetCode] 366. Find Leaves of Binary Tree 找二叉树的叶节点
- [LeetCode] 298. Binary Tree Longest Consecutive Sequence 二叉树最长连续序列
- [LeetCode] 110. Balanced Binary Tree 平衡二叉树
- [LeetCode] 121. Best Time to Buy and Sell Stock 买卖股票的最佳时间
- [LeetCode] 102. Binary Tree Level Order Traversal 二叉树层序遍历
- leetcode 105 从前序与中序遍历序列构造二叉树
- leetcode 144 145 94二叉树的三种非递归遍历
- LeetCode 485.最大连续1的个数
- 【LeetCode-Hot100-001】合并二叉树(617)