1.二叉树的前序遍历
144. 二叉树的前序遍历https://leetcode.cn/problems/binary-tree-preorder-traversal/这个题目在遍历的基础上还要求返回数组,数组里面按前序存放二叉树节点的值。
既然要返回数组,就必然要malloc一块空间,那么我们需要算出这个二叉树的节点个数,所以就创建一个函数TreeSize求出节点个数。TreeSize的实现在上篇文章有提到http://t.csdnimg.cn/izhvv
所以在preorderTraversal里面创建一个变量n来接收TreeSize的返回值,再为变量amalloc一块空间,空间大小是n个int。这个时候就要考虑如何存放前序的值,写一个函数PrevOrder,参数是头指针root,数组a,指针变量pi,进入函数首先判断当前节点是否为空,如果是空则返回,不是空则开始存值,将root->val存在a[*pi]这个位置,然后(*pi)++,然后就是递归左右子树。在preorderTraversal内部创建变量i,&i作为PrevOrder参数,再将*returnsize=n,最后返回数组a即可。
int TreeSize(struct TreeNode* root)
{
return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
void PrevOrder(struct TreeNode* root,int* a,int* pi)
{
if(root==NULL)
return ;
a[(*pi)++]=root->val;
PrevOrder(root->left,a,pi);
PrevOrder(root->right,a,pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
int n=TreeSize(root);
int* a=(int*)malloc(sizeof(int)*n);
int i=0;
PrevOrder(root,a,&i);
*returnSize=n;
return a;
}
2.判断两棵树是否相同
100. 相同的树https://leetcode.cn/problems/same-tree/
首先判断这两棵树是否都是空树,如果都是空树则return true,如果没有返回true则说明有以下情况:1.p==NULL,q!=NULL. 2.p!=NULL,q==NULL. 3.q!=NULL,p!=NULL.下一步就是判断,既然有一棵树为NULL,那么如果另一棵树不为NULL,则返回false,巧妙地利用||逻辑运算符,因为已知走到这一步至少有一棵树不为NULL,所以两个条件至少有一个不成立,||运算符是有一个成立则成立,所以如果另一棵树为NULL则返回false,那么现在只剩下一种情况,两棵树都不为空。这个时候判断当前两棵树的节点的值是否相同即可,如果不相等则返回false。最后递归左右子树,这里需要注意的是,如果左树已经不相同而返回false的话就没必要走右树了,所以使用&&逻辑运算符。
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
//都为空
if(p==NULL&&q==NULL)
return true;
//其中一个为空
if(p==NULL||q==NULL)
return false;
if(q->val!=p->val)
return false;
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
3.判断一棵树是否为另一棵树的子树
572. 另一棵树的子树https://leetcode.cn/problems/subtree-of-another-tree/
这里我们可以拷贝上一题的代码,判断是否树相同。首先判断root这棵树是否为空树,如果是空树则返回false。再判断root的值val是否与subRoot的值val相同,如果相同则使用isSameTree判断从当前节点开始两棵树是否相同,如果相同则返回true。最后递归判断一下root的左子树和右子树,这里可以使用||逻辑运算符,因为无论是左边还是右边,有一边中的子树和subRoot相同即可。
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
//都为空
if (p == NULL & q == NULL)
return true;
//其中一个为空
if (p == NULL || q == NULL)
return false;
if (q->val != p->val)
return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
if(root==NULL)
return false;
if(root->val==subRoot->val)
{
if(isSameTree(root,subRoot))
return true;
}
return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}
今天的分享到这里就结束了,感谢大家的阅读!