2022_08_10_106期__二叉树

目录

 

求第k层的节点个数：

返回x所在的节点。

力扣：

---

求第k层的节点个数：

我们要求第k层的节点的个数：

假如我们的k为1时，对应的节点个数为1，加入我们的k为2时，我们可以求1节点对应的子节点数目，加入我们的k为3时，我们可以求第2层的节点对应的子节点的数目：

 我们画图演示求第三层的节点个数

 2的左子节点为3，3的左子节点为NULL，3的右节点为NULL，2的右节点为NULL。所以只有一个子节点，返回1

4的左节点为5，5的左右节点都为NULL，4的右节点为6，6的左右节点都为NULL，所以4节点的子节点有两个，分别是5和6.

所以第三层的节点的个数为1+2等于3.

我们用代码进行实现：

int TreeKLevel(BTNode*root, int k)
{
	assert(k > 0);
	if (k == 1)
	{
		return 1;
	}
	if (root== NULL)
	{
		return 0;
	}
	return TreeKLevel(root->left,k-1)
		+ TreeKLevel(root->right,k-1);
}

所以代码的核心思想就是求第k-1层节点对应的子节点的数目。

返回x所在的节点。

BTNode*TreeFind(BTNode*root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode*lret = TreeFind(root->left, x);
	if (lret)
		return lret->data;
	BTNode*rret = TreeFind(root->right, x);
	if (rret)
		return rret->data;
	return NULL;
}

力扣：

力扣

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p==NULL&&q==NULL)
        {
            return true;
        }
        if(p==NULL||q==NULL)
        {
            return false;
        }
        if(p->val!=q->val)
        {
            return false;
        }
        return isSameTree(p->left,q->left)
        &&isSameTree(p->right,q->right);
    }
};

当p和q为空指针时，表示是两个空树，空树也是相同的数。

当p和q有一个为空指针时，p和q对应的值一定不相同，对应的树一定不相等。

当p和q都不为空指针，并且p对应的值和q对应的值不相等的时候，对应的树不相等。

剩下的结果就是p和q对应的值相等。

return isSameTree(p->left,q->left)
        &&isSameTree(p->right,q->right);

当两个树对应的左子节点和右子节点都相等的时候，返回的为真。

力扣

class Solution {
public:
    bool isUnivalTree(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);
    }
};

力扣

 bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p==NULL&&q==NULL)
        {
            return true;
        }
        if(p==NULL||q==NULL)
        {
            return false;
        }
        if(p->val!=q->val)
        {
            return false;
        }
        return isSameTree(p->left,q->left)
        &&isSameTree(p->right,q->right);
    }
class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(root==NULL)
        return false;
        if(isSameTree(root,subRoot))
        return true;
        return isSubtree(root->left,subRoot)
        ||isSubtree(root->right,subRoot);
    }
};

力扣

int TreeSize(struct TreeNode*root)
 {
     if(root==NULL)
     return 0;
     return TreeSize(root->left)+TreeSize(root->right)+1;
 }
 void preorder(int *a,struct TreeNode*root,int i)
 {
     if(root==NULL)
     return ;
     a[i++]=root->val;
     preorder(a,root->left,i);
     preorder(a,root->right,i);
 }
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int n=TreeSize(root);
    int*a=(int*)malloc(sizeof(int)*n);
    *returnSize=n;
    int i=0;
    preorder(a,root,i);
    return a;
}

我们进行测试：

 问题出现在i这里

void preorder(int *a,struct TreeNode*root,int i)
 {
     if(root==NULL)
     return ;
     a[i++]=root->val;
     preorder(a,root->left,i);
     preorder(a,root->right,i);
 }

我们的i的变化并不会影响接下来递归中的i值，我们画图进行解释：

假如我们要前序遍历的数组元素为1，2，3

 我们先放1，i++

我们再放2，i++。

但是我们这里的i++并不会影响preorder(a,root->right,i)中的i，所以我们把3也放在了2处，所以对应的结果为：

正确的写法：

int TreeSize(struct TreeNode*root)
 {
     if(root==NULL)
     return 0;
     return TreeSize(root->left)+TreeSize(root->right)+1;
 }
 void preorder(int *a,struct TreeNode*root,int*pi)
 {
     if(root==NULL)
     return ;
     a[*pi]=root->val;
     (*pi)++;
     preorder(a,root->left,pi);
     preorder(a,root->right,pi);
 }
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int n=TreeSize(root);
    int*a=(int*)malloc(sizeof(int)*n);
    *returnSize=n;
    int i=0;
    preorder(a,root,&i);
    return a;
}