.对称二叉树

这道题我们可以把它分为三个子问题分别是根与根、左子树与左子树、右子树与右子树之间的比较而且最好是用前序的方式即先比较根要是根都不相等后面的就不用比较了而子树也可以在再分为根、左子树、右子树......直到不能分为止所以每次递归调用如果根的值不相等就返回false如果相等就继续往下比较。

代码如下

true;}//只有一个为空if(pNULL||qNULL){return

false;}//全不为空if(p-val!q-val){return

false;}return

isSameTree(p-left,q-left)isSameTree(p-right,q-right);

这道题思路很简单也是分为查找根、左子树、右子树三个子问题先找根的值如果相等就返回根节点如果不等继续找左子树如果相等返回左子树的节点如果不相等继续找右子树如果相等返回右子树节点如果不等则继续上面过程。

但是这道题我们要求返回的是节点所以在某次递归中如果找到了节点就要先把它保存下来然后再返回到这次递归的上一级如果不保存那节点极大可能返回不到函数外面。

总而言之递归是一级一级往上返回的如果递归有返回值每次递归都要确保能接收到下一次递归返回的值。

代码如下

(BTNode*)malloc(sizeof(BTNode));if

(node

这道题我们可以先比较根节点和左子树的值然后比较根节点和右子树的值当左子树不为空且它和根节点的值不相等时返回false当右子树不为空且它和根节点的值不相等时返回false当左右子树都和根节点相等时继续递归直到rootNULL返回true这时truetruetrue返回true。

代码如下

true;}if(root-left!NULLroot-val!root-left-val){return

false;}if(root-right!NULLroot-val!root-right-val){return

false;}return

isUnivalTree(root-left)isUnivalTree(root-right);

4.对称二叉树

这道题默认有一个根节点该节点不用比较所以我们可以比较根节点下的左子树和右子树这就需要两个参数我们可以把左子树的根节点和右子树的根节点作为左根和右根传给函数_isSymmetric()然后把左根的左子树和右根的右子树比较左根的右子树和右根的左子树比较如果不等返回false如果相等继续递归直到全部为空返回truetruetruetrue返回true。

代码如下

TreeNode*rightRoot){//全部为空if(leftRootNULLrightRootNULL){return

true;}//只有一个为空if(leftRootNULL||rightRootNULL){return

false;}//全不为空if(leftRoot-val!rightRoot-val){return

false;}return

_isSymmetric(leftRoot-left,rightRoot-right)_isSymmetric(rightRoot-left,leftRoot-right);}

bool

_isSymmetric(root-left,root-right);

题目链接力扣LeetCode

这道题看起来很简单只需要按照根、左子树、右子树的顺序依次访问即可但是有很多坑

需要自己malloc数组但是数组大小不知道所以还要写一个函数用来计算二叉树大小

malloc数组之后就不能在原函数中写递归了否则每次递归都会malloc一个空间所以又得专门写一个递归的函数。

3.二叉树节点的值要存储到数组中必然要使用下标但是下标在调用中不能传值否则每次递归调用后栈帧销毁栈帧中形参i后的值不能返回上一级递归往数组中存放数据就会出错。

int

rootNULL?0:TreeSize(root-left)TreeSize(root-right)1;}void

TreeNode*

i){if(rootNULL){return;}a[i]root-val;_preorderTraversal(root-left,a,i);_preorderTraversal(root-right,a,i);}

int*

{*returnSizeTreeSize(root);int*a(int*)malloc(*returnSize*sizeof(int));int

a,i);return

rootNULL?0:TreeSize(root-left)TreeSize(root-right)1;}void

TreeNode*

pi){if(rootNULL){return;}a[(*pi)]root-val;_preorderTraversal(root-left,a,pi);_preorderTraversal(root-right,a,pi);}

int*

{*returnSizeTreeSize(root);int*a(int*)malloc(*returnSize*sizeof(int));int

a,i);return

这道题本质还是找两颗相同的树只不过一个树必须得是另外一个树的子树那我们可以复用上文中“相同的树”的代码然后遍历找到第一棵树的所有子树与第二棵树比较如果不同继续遍历只要左右子树中有一个子树与第二颗树相同就返回true。

题目链接力扣LeetCode

true;}//只有一个为空if(pNULL||qNULL){return

false;}//全不为空if(p-val!q-val){return

false;}return

isSameTree(p-left,q-left)isSameTree(p-right,q-right);

}bool

false;}if(isSameTree(root,subRoot)){return

true;}return

isSubtree(root-left,subRoot)||isSubtree(root-right,subRoot);

层序遍历

二叉树的层序遍历是一层一层往下走的我们可以用队列来实现它用队列保存二叉树每一层的节点先让根节点入队保存并打印根节点的值然后根节点出队让它的左右孩子入队相当于第一层出队的同时带第二层入队一层带一层直到队列中所有节点都为NULL就说明二叉树遍历结束了。

层序需要队列的代码这里只列出层序的核心代码关于队列部分的代码可以在栈与队列章节中找到

数据结构-栈和队列一-CSDN博客

QueueFront(q);QueuePop(q);printf(%d

front-data);if

(front-left)QueuePush(q,front-left);if

(front-right)QueuePush(q,front-right);}printf(\n);DestoryQueue(q);

注意这里就是三层嵌套了队列Queue中有头尾节点和队列大小size头尾节点中有next指针和数据data而数据data中存放的是二叉树的节点指针所以我们在Queue.h中要把数据类型改成二叉树节点指针

所以我们每次pop的都是队列的节点而front是指向二叉树节点的指针它没有被pop所以可以找到二叉树节点的数据和它的左右孩子。

二叉树销毁最好用后序先销毁左右子树最后销毁根节点不建议使用前序否则先销毁根节点就找不到左右子树了又要重新构建二叉树比较麻烦。

void

NULL){return;}BTreeDestory(root-left);BTreeDestory(root-right);free(root);

7.二叉树遍历

相当于给一个字符串要求把给字符串恢复成一个二叉树然后输出它的中序遍历那abc##de#g##f###它是前序遍历的我们就用前序把它恢复成二叉树

代码如下

(BTNode*)malloc(sizeof(BTNode));if

(node

BTNode*CreateTree(char*a,int*pi)

NULL;}BTNode*rootBuyNode(a[*pi]);(*pi);root-leftCreateTree(a,pi);root-rightCreateTree(a,pi);return

root;

{if(rootNULL){return;}InOrder(root-left);printf(%c

,root-data);InOrder(root-right);}

int

i0;BTNode*rootCreateTree(a,i);InOrder(root);printf(\n);return

这道题就要使用到层序遍历了我们说层序遍历是一层带一层的入队和出队的过程而完全二叉树的每一层都是按顺序排放的让它的每一层数据入队然后出队直到遇见空如果是完全二叉树那此时最后一个数据出队后后面应该全为NULL而非完全二叉树就不全是NULL了如下图

所以当我们遇到空时就跳出循环然后判断后面的是否全为空一旦有非空那就不是完全二叉树。

代码如下

QueueFront(q);QueuePop(q);//遇到空就跳出if

(front

front-right);}//检查后面的节点有没有非空//有非空就不是完全二叉树while

front

对二叉树增加一个度为1的节点就一定会减少一个度为0的节点同时增加的这个节点度也为0此时度为0和度为2的节点个数相当于没变

而增加一个度为2的节点就一定会减少一个度为1的同时会增加一个度为0的节点

下面我们来做道题

假设度为0的节点有n0个度为1的有n1个度为2的有n2个根据上文学过的性质可得

n0-12n而此时要整除叶子节点一定是整数个n1必然是1所以可得n0

2n/2

好了到今天为止我们二叉树就告一段落了其实二叉树还有很多问题这些留到后面C的时候学习