二叉树经典问题
一、结点个数
方法一：count计数
//节点个数 int count = 0; void BTreeSize(BTNode* root) { if (root == NULL) //如果为空 return; ++count; BTreeSize(root->left); BTreeSize(root->right); }
缺点在于会有多线程安全问题，如果几个程序同时调用会发生错乱
方法二：遍历+传址计数
//节点个数 void BTreeSize(BTNode* root, int* pCount) { if (root == NULL) //如果为空 return; ++(*pCount); BTreeSize(root->left, pCount); BTreeSize(root->right, pCount); }
传地址解决多线程问题，但是每次计数都要重置count为0，代码不美观
方法三：
直接利用子问题的思想来写，返回当root为空则0，不是就递归左树+右树+1。
- 空树，最小规模子问题，结点个数返回0
- 非空，左子树结点个数+右子树结点个数 + 1（自己）
int BTreeSize(BTNode* root) { return root == NULL ? 0 : BTreeSize(root->left) + BTreeSize(root->right) + 1; }
总结：
上述算法思想其实就是分治思想。
把复杂的问题分成更小规模的子问题，子问题再分成更小规模的子问题……直到子问题不可再分割，直接能出结果。
二、 叶结点个数
- 思路1：遍历+计数
在遍历的基础上如果结点的左右子树均为空则count++。但是此题我们依旧采用分治思想
- 思路2：分治思想
首先，如果为空，直接返回0，如若结点的左子树和右子树均为空，则为叶节点，此时返回1，其它的继续分治递归。
- 代码演示：
//叶结点个数 int BTreeLeafSize(BTNode* root) { if (root == NULL) return 0; //为空，返回0 if (root->left == NULL && root->right == NULL) return 1; //如果左右子树均为空，则为叶结点，返回1 return BTreeLeafSize(root->left) + BTreeLeafSize(root->right); //继续分治递归 }
三、 第K层结点个数
- 思路：
假设K=3
- 空树，返回0
- 非空，且K == 1，返回1
- 非空，且K>1，转换成左子树K-1层节点个数 + 右子树K-1层节点个数
- 代码演示：
//第K层节点个数,K>=1 int BTreeKLevelSize(BTNode* root, int k) { assert(k >= 1); if (root == NULL) return 0; if (k == 1) return 1; return BTreeKLevelSize(root->left, k - 1) + BTreeKLevelSize(root->right, k - 1); }
四、二叉树的深度
- 思路：
此题同样是运用分治的思想来解决，要比较左子树的高度和右子树的高度，大的那个就+1，因为还有根结点也算1个高度。
- 代码演示：
//求树的深度 int BTreeDepth(BTNode* root) { if (root == NULL) return 0; int leftDepth = BTreeDepth(root->left); //左子树高度 int rightDepth = BTreeDepth(root->right);//右子树高度 return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1; }
五、 二叉树查找值为x的节点
- 思路：
还是利用分治的思想，将其递归化成子问题去解决
- 先去根结点寻找，是就返回此节点
- 此时去左子树查找有无节点x
- 最后再去右子数去查找有无节点x
- 若左右子树均找不到节点x，直接返回空
- 代码演示：
//二叉树查找值为x的节点 BTNode* BTreeFind(BTNode* root, BTDataType x) { //如果根节点为空，直接返回空 if (root == NULL) return NULL; //如果找到节点，直接返回节点位置 if (root->data == x) return root; //若没找到，去左子树找 BTNode* ret1 = BTreeFind(root->left, x); if (ret1) return ret1; //此时左子树没找到，去右子树找 BTNode* ret2 = BTreeFind(root->right, x); if (ret2) return ret2; //若左子树和右子树都每找到，直接返回空 return NULL; }
测试：
#include<iostream> #include<string> #include<stdlib.h> using namespace std; //创建二叉链结构 typedef int BTDataType; //本文以int整型为例 typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; int data; }BTNode; //创建结点 BTNode* BuyBTNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { printf("malloc fail\n"); exit(-1); } node->data = x; node->left = node->right = NULL; return node; } //构建树 BTNode* CreatBinaryTree() { //创建6个结点 BTNode* node1 = BuyBTNode(1); BTNode* node2 = BuyBTNode(2); BTNode* node3 = BuyBTNode(3); BTNode* node4 = BuyBTNode(4); BTNode* node5 = BuyBTNode(5); BTNode* node6 = BuyBTNode(6); //将结点连接起来，构成自己想要的树 node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6; //返回根结点 return node1; } //二叉树查找值为x的节点 BTNode* BTreeFind(BTNode* root, BTDataType x) { //如果根节点为空，直接返回空 if (root == NULL) return NULL; //如果找到节点，直接返回节点位置 if (root->data == x) return root; //若没找到，去左子树找 BTNode* ret1 = BTreeFind(root->left, x); if (ret1) return ret1; //此时左子树没找到，去右子树找 BTNode* ret2 = BTreeFind(root->right, x); if (ret2) return ret2; //若左子树和右子树都每找到，直接返回空 return NULL; } int main() { BTNode* tree = CreatBinaryTree(); for (int i = 0; i <= 7; i++) { printf("Find:%d,%p\n", i, BTreeFind(tree, i)); } return 0; }
六、二叉树的销毁
- 思路：
销毁的思想和遍历类似，如若我挨个遍历的同时，没遍历一次就销毁一次，岂不能达到效果，但是又会存在一个问题，那就是你要采用什么样的遍历方式？倘若你采用前序遍历，刚开始就把根销毁了，那么后面的子树还怎么销毁呢？因为此时根没了，子树找不到了就，所以要采用倒着销毁的规则，也就是后续的思想
代码演示：
//二叉树的销毁 void BTreeDestory(BTNode* root) { if (root == NULL) return; BTreeDestory(root->left); BTreeDestory(root->right); free(root); root = NULL; }
七、 判断二叉树是否是完全二叉树
完全二叉树的概念：前k-1层是满的，最后一层是连续的。
思路：层序遍历+变形
通过上图，不难发现，如果是完全二叉树的话，在层序遍历的时候是不会出现间隔的NULL。例如第一幅图就不是完全二叉树，因为层序遍历到第三层的时候会出现间隔NULL，因为3 -> NULL -> 5 -> 6，而剩余两幅图均不会出现这样的问题，接下来，我将利用类似的思想解决这道题。
层序遍历明确指出，当其中一个结点pop出来时，要把它的孩子给push进队列里，但前提是把不为空的孩子给push进去，现在规矩变了，不管你是否为空，都给push进去，也就是说出一个结点，push两个孩子结点，使其停止的条件是当我pop出来的结点为NULL时，此时停止push，一直pop到队列为空，如果全是空，就是完全二叉树，如果有非空，就不是。
总结
层序遍历，空节点也进队列
出到空节点以后，出队列中所有数据，如果全是空，就是完全二叉树，如果有非空，就不是
- 图示：
- 代码演示：
//判断一颗二叉树是否是完全二叉树 bool BTreeComplete(BTNode* root) { Queue q; QueueInit(&q); if (root) { QueuePush(&q, root); //根结点不为空，入队列 } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); //删除队头数据，方便后续取队头数据 if (front == NULL) //如果取队头为空，停止，接下来进入下一个while循环判断是否为完全二叉树 break; QueuePush(&q, front->left); QueuePush(&q, front->right); } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); //如果空出到非空，那么说明不是完全二叉树 if (front) { QueueDestory(&q); return false; } } QueueDestory(&q); return true; //全是空，此时返回true，为完全二叉树 }
二叉树的实现
函数接口：
typedef char BTDataType; typedef struct BinaryTreeNode { BTDataType _data; struct BinaryTreeNode* _left; struct BinaryTreeNode* _right; }BTNode; // 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树 BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi); // 二叉树销毁 void BinaryTreeDestory(BTNode** root); // 二叉树节点个数 int BinaryTreeSize(BTNode* root); // 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root); // 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k); // 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x); // 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root); // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root); // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root); // 层序遍历 void BinaryTreeLevelOrder(BTNode* root); // 判断二叉树是否是完全二叉树 int BinaryTreeComplete(BTNode* root);
函数实现：
#include "BTree.h" #include "queue.h" //参考之前的代码 #include "stack.h" BTNode *BinaryTreeCreate(BTDataType * src, int n, int* pi) { if (src[*pi] == '#' || *pi >= n) { (*pi)++; return NULL; } BTNode * cur = (BTNode *)malloc(sizeof(BTNode)); cur->_data = src[s_n]; (*pi)++; cur->_left = BinaryTreeCreateExe(src); cur->_right = BinaryTreeCreateExe(src); return cur; } void BinaryTreePrevOrder(BTNode* root) { if (root) { putchar(root->_data); BinaryTreePrevOrder(root->_left); BinaryTreePrevOrder(root->_right); } } void BinaryTreeInOrder(BTNode* root) { if (root) { BinaryTreeInOrder(root->_left); putchar(root->_data); BinaryTreeInOrder(root->_right); } } void BinaryTreePostOrder(BTNode* root) { if (root) { BinaryTreePostOrder(root->_left); BinaryTreePostOrder(root->_right); putchar(root->_data); } } void BinaryTreeDestory(BTNode** root) { if (*root) { BinaryTreeDestory(&(*root)->_left); BinaryTreeDestory(&(*root)->_right); free(*root); *root = NULL; } } void BinaryTreeLevelOrder(BTNode* root) { Queue qu; BTNode * cur; QueueInit(&qu); QueuePush(&qu, root); while (!QueueIsEmpty(&qu)) { cur = QueueTop(&qu); putchar(cur->_data); if (cur->_left) { QueuePush(&qu, cur->_left); } if (cur->_right) { QueuePush(&qu, cur->_right); } QueuePop(&qu); } QueueDestory(&qu); } int BinaryTreeComplete(BTNode* root) { Queue qu; BTNode * cur; int tag = 0; QueueInit(&qu); QueuePush(&qu, root); while (!QueueIsEmpty(&qu)) { cur = QueueTop(&qu); putchar(cur->_data); if (cur->_right && !cur->_left) { return 0; } if (tag && (cur->_right || cur->_left)) { return 0; } if (cur->_left) { QueuePush(&qu, cur->_left); } if (cur->_right) { QueuePush(&qu, cur->_right); } else { tag = 1; } QueuePop(&qu); } QueueDestory(&qu); return 1; }
二叉树OJ练习
965. 单值二叉树 - 力扣（LeetCode）
思路：
如果每个根和其左右孩子都相等，那么我们就可以断定此二叉树必是单值二叉树，因为根节点也会成为孩子，孩子也会成为根结点，所以采用分治思想
bool isUnivalTree(struct TreeNode* root) { if (root == NULL) { return true; //如果为空树，同样符合单值，直接返回true } if (root->left && root->left->val != root->val) { return false;//如果左孩子存在并且左孩子和根结点不同，返回false } if (root->right && root->right->val != root->val) { return false;//如果右孩子存在并且右孩子和根结点不同，返回false } return isUnivalTree(root->left) && isUnivalTree(root->right);//递归+分治，转化子问题 }
100. 相同的树 - 力扣（LeetCode）
思路：
非常简单，要先排除些特殊情况，如若两棵树的根节点均为空，那么符合题意，如若有任何一棵树先为空，那么同样不符合，其次就是判断节点值是否相等，最后就是最基本的递归（递归左子树和右子树）+分治即可解决此问题。
bool isSameTree(struct TreeNode* p, struct TreeNode* q) { //都是空树 if (p == NULL && q == NULL) { return true; //如果p和q均为NULL，成立，返回true } //一个为空，一个不为空 if (p == NULL || q == NULL) { return false; //若p和q其中一个先为空，那么不相同，返回false } //都不为空 if (p->val != q->val) { return false; //如果对应子树的值不同，同样返回false } return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);//分治+递归 }
顺便击败了全世界的人，哈哈哈
101. 对称二叉树 - 力扣（LeetCode）
思路：
因为是对称，所以左子树的右树与右子树的左树相同，利用辅助函数传左右子树，然后利用上题代码判断 左子树的右树与右子树的左树是否相同（再在主函数使用递归+分治的思想转换成子问题继续比较其余的节点）
//辅助函数比较对称的值是否相等 bool _isSymmetric(struct TreeNode* p, struct TreeNode* q) { if (p == NULL & q == NULL) { return true; //如果p和q均为NULL，成立，返回true } if (p == NULL || q == NULL) { return false; //若p和q其中一个先为空，那么不相同，返回false } if (p->val != q->val) { return false; //如果对应子树的值不同，同样返回false } return _isSymmetric(p->left, q->right) && _isSymmetric(p->right, q->left);//分治+递归 } bool isSymmetric(struct TreeNode* root) { if (root == NULL) { return true; } return _isSymmetric(root->left, root->right); }
572. 另一棵树的子树 - 力扣（LeetCode）
思路：
遍历左边的树的每一个结点，作子树的根，跟右边的子树都比较一下，此时我们就可以单独封装一个先前写过的函数isSameTree，用来比较两棵树是否相同，依次比较，若是子树，返回true
//辅助函数，专门判断两棵树是否相同 bool isSameTree(struct TreeNode* root, struct TreeNode* subRoot) { if (root == NULL && subRoot == NULL) { return true; } if (root == NULL || subRoot == NULL) { return false; } if (root->val != subRoot->val) { return false; } return isSameTree(root->left, subRoot->left) && isSameTree(root->right, subRoot->right); } bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) { if (root == NULL) { return false; //根都为空了，何来子树，直接返回false } if (isSameTree(root, subRoot)) { return true; //是子树就返回true } return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot); }
二叉树遍历_牛客题霸_牛客网 (nowcoder.com)
思路:
题目中还有一个要求，在根据字符串创建树时是按照先序的遍历方式创建的，也就是根->左子树->右子树
首先遇到a，不是#，继续往下构建左子树b，再往下构建左子树c，再递归构建c的左子树为#，也就是空，此时递归c的右子树#为空，递归回来链到b的右子树d，继续构建d的左子树e，构建e的左子树#为空，递归返回构建e的右子树g，再递归g的左右子树均为空，递归返回d的右子树f，构建f的左右子树均为#空，递归返回a的右子树#为空，至此构建树结束
如图：
当我们创建好二叉树的结构后，只需要将其按照题意中序遍历的方式打印出来即可
#include<stdio.h> //创建二叉树结构 typedef struct BinaryTreeNode { char data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; //创捷结点，先序结构创建 BTNode* CreateTree(char* a, int* pi) { if (a[*pi] == '#') { (*pi)++; return NULL; } BTNode* root = (BTNode*)malloc(sizeof(BTNode)); root->data = a[(*pi)++]; root->left = CreateTree(a, pi); root->right = CreateTree(a, pi); return root; } void InOrder(BTNode* root) { if (root == NULL) return; InOrder(root->left); printf("%c ", root->data); InOrder(root->right); } int main() { char a[100]; scanf("%s", a); int i = 0; BTNode* tree = CreateTree(a, &i); InOrder(tree); return 0; }
