1. 二叉树构建（通过完全二叉树数组）
Node* build_tree(int* t, int n, int i)
{
if (i > n || t[i - 1] < 0) return nullptr;
Node* pl = build_tree(t, n, i * 2);
Node* pr = build_tree(t, n, i * 2 + 1);
return new Node(t[i - 1], pl, pr);
}
void pre(Node* t)
{
if(!t) return;
cout << t->value << endl;
pre(t->left);
pre(t->right);
}
int t[7] = { 5, 1, 4, -1, -1, 3, 6}; // -1为空
Node* tree = build_tree(t, 7, 1); // 创建二叉树，第三个参数为1
pre(tree);
// 5
// /
// 1 4
// /
// 3 6
2. 翻转二叉树
// 把树所有节点的左右都翻转
TreeNode* inverse(TreeNode* root)
{
if (!root) return nullptr;
swap(root->left, root->right);
inverse(root->left);
inverse(root->right);
return root;
}
3. Leetcode 98. 验证二叉搜索树
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
输入:
5
/
1 4
/
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
class Solution {
public:
bool isValidBST(TreeNode* root) {
long min_value, max_value; bool valid;
dfs(root, &min_value, &max_value, &valid);
return valid;
}
void dfs(TreeNode* root, // 全部用指针传递结果
long *min_val, long *max_val, bool *valid) {
// 边界处理
if (root==nullptr) {
*min_val = LONG_MAX;
*max_val = LONG_MIN;
*valid = true;
return;
}
// 搜索
long l_min_val, l_max_val; bool l_valid;
dfs(root->left, &l_min_val, &l_max_val, &l_valid);
long r_min_val, r_max_val; bool r_valid;
dfs(root->right, &r_min_val, &r_max_val, &r_valid);
// 值传递
if(l_max_val<root->val&&r_min_val>root->val)
*valid = l_valid && r_valid;
else *valid = false;
*max_val = max(r_max_val, (long)root->val);
*min_val = min(l_min_val, (long)root->val);
}
};
4. 判断是否是平衡二叉树
bool isBalance(TreeNode* root, int* depth)
{
if (!root) {
*depth = 0; // 记录深度
return true;
}
int ld, rd;
if (isBalance(root->left, &ld) && isBalance(root->right, &rd)) {
if (abs(ld - rd) <= 1) {
*depth = 1 + (ld > rd ? ld : rd);
return true;
}
}
return false;
}
5. 二叉树k层节点个数
int getkNum(Node* root, int k)
{
if (!root || k <= 0) return 0;
if (k == 1) return 1;
return getkNum(root->left, k - 1) + getkNum(root->right, k - 1);
}
6. 二叉树找最近公共祖先
// 非常非常经典，建议背出
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL || root==p || root==q) return root; // 要么是NULL，要么是p或q
// 向左(右)找p或q，找到返回p或q或公共祖先，找不到返回NULL
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);
if(left!=NULL && right!=NULL) return root; // 两边都找到，root肯定是最近公共祖先
else return left!=NULL?left:right;
// 因为假设必须存在公共祖先，所以递归的最上层必须会返回公共祖先，而不是p或q
}
7. 二叉树中最大路径和
题目： https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
类似动态规划方法，只是用到了回溯
int find(TreeNode *root, int &maxm) {
if(root==NULL) return 0;
int left_max = find(root->left, maxm);
int right_max = find(root->right, maxm);
maxm = max(maxm, left_max+root->val+right_max);
int res = max(left_max, right_max) + root->val;
return max(0, res);
}
int maxPathSum(TreeNode* root) {
int maxm=-999999999;
find(root, maxm);
return maxm;
}
8. 二叉树中序非递归
// 直接背
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
auto p = root;
while (p || !st.empty()) { // p和st必须全部清空才能退出
// 第一步，向左一条路走到黑
while (p) {
st.push(p);
p = p->left;
}
// 第二步，退栈向右试探
auto node = st.top();
st.pop();
res.emplace_back(node->val);
p = node->right;
}
return res;
}
9. 二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。
一棵二叉树的直径长度是任意两个结点路径长度中的最大值。
这条路径可能穿过也可能不穿过根结点。
给定二叉树
1
/
2 3
/
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
这道题与 7 题类似
int find(TreeNode *root, int &maxm) {
if(root==NULL) return 0;
int left_max = find(root->left, maxm);
int right_max = find(root->right, maxm);
maxm = max(maxm, left_max + right_max);
return max(left_max, right_max) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
int maxm=0;
find(root, maxm);
return maxm;
}
10. 二叉树之字形遍历
// 层次遍历，奇数层逆序输出
// 下面这个代码很好地展现了层次遍历，并记录层次编号的方案
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode*> q;
if (root) q.push(root);
bool lr = true;
while (!q.empty()) {
int size = q.size(); // 先查看size，再按size压入
vector<int> level(size, 0);
while (size--) {
root = q.front(); q.pop();
level[lr ? level.size() - size - 1 : size] = root->val;
if (root->left) q.push(root->left);
if (root->right) q.push(root->right);
}
res.push_back(level);
lr = !lr;
}
return res;
}
11. 二叉搜索树插入
TreeNode* insertIntoBST(TreeNode* root, int val) {
// 直接插在最后面
if(!root) return new TreeNode(val);
if(root->val < val) root->right = insertIntoBST(root->right, val);
else root->left = insertIntoBST(root->left, val);
return root;
}
12. 二叉搜索树删除
// 非常漂亮！！必背！！
TreeNode* deleteNode(TreeNode* root, int key) {
if(!root) return root;
if(key<root->val)root->left=deleteNode(root->left,key);
if(key>root->val)root->right=deleteNode(root->right,key);
if(key==root->val){
if(!root->left&&!root->right)return NULL;
if(root->left&&!root->right)return root->left;
if(!root->left&&root->right)return root->right;
// 用中序下一个节点值替换，然后再递归删后面的
TreeNode* temp=root->right;
while(temp->left)temp=temp->left;
root->val=temp->val;
root->right=deleteNode(root->right,root->val);
}
return root;
}
13. 二叉树最大宽度
给定一个二叉树，编写一个函数来获取这个树的最大宽度。
树的宽度是所有层中的最大宽度。
这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
输入:
1
/
3 2
/
5 3 9
输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。
int widthOfBinaryTree(TreeNode* root) {
vector<int> level_first_index;
int maxw=0;
dfs(root, 1, 1, level_first_index, maxw);
return maxw;
}
// dfs就能传树节点在完全二叉树上的index
void dfs(TreeNode *root, int level, int index,
vector<int> &level_first_index, int &maxw)
{
if(!root) return;
// 关键：记录第一个到达level深度的节点index
if(level>level_first_index.size()) level_first_index.push_back(index);
maxw = max(maxw, index-level_first_index[level-1]+1);
dfs(root->left, level+1, index*2, level_first_index, maxw);
dfs(root->right, level+1, index*2+1, level_first_index, maxw);
}
14. 判断是否是二叉搜索树的后序序列
// 经典分治做法
bool verifyPostorder(vector<int>& postorder) {
if(postorder.size() == 0)return true;
int end = postorder.size() - 1;
return judge(postorder, 0, end);
}
bool judge(vector<int> &postorder, int begin , int end){
//只剩一个节点直接返回true
if(begin >= end) return true;
int i = begin , index = 0;
//找到序列中比最右侧结点值大的那个结点
for(; i < end ; i++) if(postorder[i] >= postorder[end]) break;
//分治之前要满足的条件
index = i ;
while(i < end) if(postorder[i++] < postorder[end]) return false;
//左右两边进行分治
return judge(postorder, begin , index - 1) && judge(postorder , index , end - 1);
}
15. 判断树t是不是树s的子树
class Solution {
public:
bool isSametree(TreeNode* s, TreeNode* t) {
if(!s&&!t) return true;
if(!s||!t) return false;
if(s->val == t->val) {
return isSametree(s->left, t->left) && isSametree(s->right, t->right);
}
else return false;
}
bool isSubtree(TreeNode* s, TreeNode* t) {
if(!s&&!t) return true;
if(!s||!t) return false;
return isSametree(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t);
}
};
16. 先序中序构建二叉树
BitTree *createBinTreeByPreIn(char *preOrder,char *inOrder,int number)
{
if(number==0) return NULL; // 边界条件仅为长度为0
char c = preOrder[0]; // 先序第一个
int i = 0;
while(i<number && inOrder[i]!=c) i++; // 找到它在中序中的位置
int leftNumber = i; // 确定左右的长度
int rightNumber = number - i - 1;
BitTree *node = (BitTree *)malloc(sizeof(BitTree)); // 创建节点
node->data = c;
node->lchild = createBinTreeByPreIn(&preOrder[1], &inOrder[0], leftNumber);
node->rchild = createBinTreeByPreIn(&preOrder[leftNumber+1],
&inOrder[leftNumber+1], rightNumber);
return node;
}