1.输入k ,找第k层节点个数
int TreeKlevel(BTNode*root,int k) {
if (root == NULL) {
return 0;
}
if (k == 1) {
return 1;
}
return TreeKlevel(root->left, k - 1)+
TreeKlevel(root->right, k - 1);
}
在这里我们要确定递归子问题,第一个就是NULL时返回,还有一个就是k=1时就是我们要找的层数。
2.输入一个数,查找该数,找到了返回其地址。
BTNode* TreeFind(BTNode* root, int x) {
if (root == NULL) {
return NULL;
}
if (root->val == x) {
return root;
}
BTNode* ret1 = TreeFind(root->left, x);
if (ret1)
return ret1;
BTNode* ret2 = TreeFind(root->right, x);
if (ret2)
return ret2;
return NULL;
}
在这里我们需要弄明白的是,在某个开辟的栈帧中找到了该数据,直接返回其指针,是得不到它的地址的。
3.判断两棵树是相同的
bool isSametree(BTNode* root1, BTNode* root2) {
//都为空
if (root1 == NULL && root2 == NULL) {
return true;
}
//其中一个为空
if (root1 == NULL || root2 == NULL) {
return false;
}
if (root1->val != root2->val) {//判断值是否相同
return false;
}
return isSametree(root1->left, root2->left) &&
isSametree(root1->right, root2->right);
}
4.判断是否为镜像/对称二叉树,也就是左右子树是否相同
bool _isSymmetric(BTNode* root1, BTNode* root2) {
//根比较
//左子树和右子树比较
//右子树和左子树比较
//都为空
if (root1 == NULL && root2 == NULL) {
return true;
}
//一个为空一个不为空
if (root1 == NULL || root2 == NULL) {//短路求值
return false;
}
if (root1->val != root2->val) {
return false;
}
return _isSymmetric(root1->left, root2->right) &&
_isSymmetric(root1->right, root2->left);
}
bool isSymmetri(BTNode* root) {
return _isSymmetric(root->left, root->right);//将根的两个子树传递给子函数
}
5.在一棵树上找另一棵树
bool issubTree(BTNode* root, BTNode* subroot) {
if (root == NULL)
return false;
if (root->val == subroot->val&& isSametree(root, subroot)) {//当遍历时发现根相同时才开始遍历比较
//为了防止不止一处地方根相同且有一处根相同的地方并不完全相等,所以我们需要这两个条件同时成立才返回true.
return true;
}
//遍历
return issubTree(root->left,subroot) || issubTree(root->right,subroot);
}
这里与其他函数结合可以更好地解决问题。
![](https://i-blog.csdnimg.cn/direct/741b67863c6f4cb2a2e52a6ac97d13e7.png)