赞
踩
目录
剑指 Offer 55 - I. 二叉树的深度 - 力扣(LeetCode)
查找二叉树中的x值
求二叉树高度那里。
- bool isUnivalTree(struct TreeNode* root){
- if(root==NULL)
- return true;
- if(root->left&&root->val!=root->left->val)
- return false;
- if(root->right&&root->val!=root->right->val)
- return false;
-
- return isUnivalTree(root->left)
- &&isUnivalTree(root->right);
- }
思路:
一:如果p和q都不等于空,那么就返回true,因为有可能是这样的:
那万一是这种的呢?
所以我们下面要设置其他条件,递归对比的时候让p的左和q的左对比,p的右和q的右对比,这样就只会出现1这种情况,不会出现2这种情况了。
二:
如果p和q其中只有一个为空,那么两个二叉树肯定不相同
三:如果p和q的值相同,那么两个二叉树就相同
那这样写:
- bool isSameTree(struct TreeNode* p, struct TreeNode* q){
- if(p==NULL&&q==NULL)
- return true;
- if(p==NULL||q==NULL)
- return false;
- if(p->val!=q->val)
- return true;
-
- return isSameTree(p->left,q->left)
- && isSameTree(p->right,q->right);
-
- }
运行看看:
为什么结果是true呢?
第一次对比相同直接把值返回了,递归就没办法往下继续对比了,剩下的节点值可能是不相同的
所以做这种题都得逆向思维,不要返回true,要返回false,这样false的部分就确定了,没确定的true部分让递归去确定。
把输入的这串字符还原成二叉树的逻辑图,#代表空。
还原如下:
是怎么还原的呢?首先把这串字符当成一个字符串数组,然后用数组下标来遍历这个字符串。
OK,接下来我们要写代码来实现一下。
数组下标不是整形,因为我们定义的pi为int* ,所以我们要解引用Pi,让它找到Int i;
pi本身就是int*型的,这里递归应该直接传pi的不应该传*pi,不然pi就成int**型了。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。