1.二叉树的前序遍历
这个题目在遍历的基础上还要求返回数组，数组里面按前序存放二叉树节点的值。
既然要返回数组，就必然要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.判断两棵树是否相同
首先判断这两棵树是否都是空树，如果都是空树则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.判断一棵树是否为另一棵树的子树
这里我们可以拷贝上一题的代码，判断是否树相同。首先判断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); }
今天的分享到这里就结束了，感谢大家的阅读！
