二叉树相关算法
二叉树相关性质：
性质一：在二叉树的第i层上至多有2^(i-1)个结点(i>=1)
性质二：深度为k的二叉树至多有2^(k-1)个结点(k>=1)
性质三：对任意一颗二叉树T，若终端结点数为n0 ,而其度数为2的结点数为n2，则n0=n2+1
性质四：具有n个结点的完全二叉树的深度为 ⌊log n⌋+1(以2为底)
满二叉树：深度为k，且有2^(k-1)个结点的二叉树。 在满二叉树中，每层结点都是满的，即每层节点都具有最大结点数。
完全二叉树：深度为k，结点数为n的二叉树，如果其结点1n的位置序号分别于满二叉树的节点1n的位置序号一一对应，则为完全二叉树。可见，满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。
题目
重建二叉树
典型题例：
输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。
示例 ：
给定： 前序遍历是：[3, 9, 20, 15, 7] 中序遍历是：[9, 3, 15, 20, 7] 返回：[3, 9, 20, null, null, 15, 7, null, null, null, null] 返回的二叉树如下所示： 3 / \ 9 20 / \ 15 7
思路
核心：
代码：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: //哈希map unordered_map<int, int> pos; TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int n = preorder.size(); //for循环中<=时，n=preorder.size() - 1 //遍历中序序列 for (int i = 0; i < n; i ++) pos[inorder[i]] = i; //在哈希表中记录每个值在中序遍历中的位置 return dfs(preorder, inorder, 0, n - 1, 0, n - 1); } TreeNode *dfs(vector<int> &pre, vector<int> &in, int pl, int pr, int il, int ir){ if(pl > pr) return nullptr; //pl为root,在中序遍历中的位置-最左端的值为左子树长度 int k = pos[pre[pl]] - il; TreeNode *root = new TreeNode(pre[pl]); //定义根结点 root->left = dfs(pre, in, pl + 1, pl + k, il, il + k - 1); //递归遍历左子树 root->right = dfs(pre, in, pl + k +1, pr, il + k + 1, ir); //递归遍历右子树 return root; } };
二叉树的下一个节点
典型题例：
给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。
注意：
- 如果给定的节点是中序遍历序列的最后一个，则返回空节点;
- 二叉树一定不为空，且给定的节点一定不是空节点；
示例 ：
输入： 假定二叉树是：[2, 1, 3, null, null, null, null]， 给出的是值等于2的节点。 则应返回值等于3的节点。 解释：该二叉树的结构如下，2的后继节点是3。 2 / \ 1 3
思路
代码：
class Solution { public: TreeNode* inorderSuccessor(TreeNode* p) { if(p->right){ //存在右子树，找到右子树最左侧的节点就是当前节点的后继 p = p->right; while(p->left) p = p->left; return p; } //无右子树，沿father域找到第一个实其father左儿子的节点，该节点的father节点是当前节点的后继 while(p->father && p == p->father->right) p = p->father; return p->father; } };
充电站
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
