【C语言】带你用偷懒的方式刷爆二叉树OJ题

本文首发于2022-04-20，2024年重新刷题，对本文做了较大更新，所以重新发布。

前言

上篇博客我带大家领略了一番链式二叉树的操作，现在让我们来看看二叉树的相关题目，一起来巩固一下知识点吧！

点我复习上一篇博客的内容！👉 传送门；

1.一些选择题

1.1

设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（ ）个
A.11
B.12
C.13  √
D.14

设Ni表示度为i的节点个数，则节点总数 N = N0 + N1 + N2
节点个数于节点边的关系： N个节点的树有N-1个边
边与度的关系：N - 1 = N1 + 2 * N2
故：N0 + N1 + N2 - 1 = N1 + 2 * N2
因此，得：N0 = N2 + 1
回到原题，N0 = 3，N1 = 8，可得N2 = 2
因此答案是 3 + 8 + 2 = 13

1.2

1 2	有N个元素的完全二叉树的深度是() 答案：logN+1

高度为h的完全二叉树，节点个数在： 2^(h - 1) - 1 < n <= 2^h - 1

即log(n + 1) <= h < log(n + 1) + 1

这里需要注意的是n左右区间的开闭问题

完全二叉树最少的节点个数是2^(h - 1)-1+1个，所以是n>2^(h - 1) - 1

1.3 由已知遍历序列画出原本树的结构

已知某二叉树的中序遍历序列为JGDHKBAELIMCF，后序遍历序列为JGKHDBLMIEFCA，则其前序遍历序列为（ ）
A.ABDGHJKCEFILM
B.ABDGJHKCEILMF   √
C.ABDHKGJCEILMF
D.ABDGJHKCEIMLF

这道题我刚开始的思路是错的，因为我把它当作完全二叉树来看待，但题目并没有说它是完全二叉树

主要思路：可以从后续遍历确定根节点为A，中序遍历可以确定A的左右子树。再继续从后序遍历中确定A左右子树的根节点，依次往下判断

所以我画了一个分析图，如下👇

已知某二叉树的前序遍历序列为ABDEC，中序遍历序列为BDEAC，则该二叉树（ ）
A.是满二叉树
B.是完全二叉树，不是满二叉树
C.不是完全二叉树   √
D.是所有的结点都没有右子树的二叉树

这道题的思路和上一道题是一样的

已知某二叉树的前序遍历序列为5 7 4 9 6 2 1，中序遍历序列为4 7 5 6 9 1 2，则其后序遍历序列为（ ）
A.4 2 5 7 6 9 1
B.4 2 7 5 6 9 1
C.4 7 6 1 2 9 5  √
D.4 7 2 9 5 6 1

本题依旧和上面两道题思路相同！

1.4 单边树

一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）
A.所有的结点均无左孩子
B.所有的结点均无右孩子
C.只有一个叶子结点
D.至多只有一个结点

如果前序遍历和后序遍历序列正好相反，说明它是一个单边树，比如下面这前序和中序序列所构成的树的结构:

12345（纵向）

54321

对于单边树，只有一个叶子节点

1.5

20.如果一颗二叉树的前序遍历的结果是ABCD，则满足条件的不同的二叉树有（ ）种

A.13
B.14 √
C.15
D.16

首先这棵二叉树的高度一定在3~4层之间:
三层：
A(B(C,D),()), A((),B(C,D)), A(B(C,()),D), A(B((),C),D),
A(B,C(D,())), A(B,C((),D))
四层：
如果为四层，就是单边树，每一层只有一个节点，除过根节点，其他节点都有两种选择，在上层节点的左边还是右边，所以2*2*2共8种
总共为14种。

2.OJ题刷起来！

KY11 二叉树遍历

牛客网 KY11 二叉树遍历 👉传送门

这道题要求我们用先序遍历的操作从一个数组中读出一个树，并构建出树的基本结构，再用中序遍历的方式打印出这颗树

之前我们学习了前序遍历的操作，这里只需要把前序遍历中的printf操作改成构建新树即可

因为涉及道i的多次调用，所以函数中的i需要取地址，必须保证多次调用的i会同步++
构建完树的节点，并赋值后，需要递归构建左右子树，最后返回节点的地址
题目中的#代表NULL，直接return空即可

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef char BTDataType;

typedef struct BTreeNode
{
	BTDataType data;
	struct BTreeNode* left;
	struct BTreeNode* right;
}BTNode;

// 二叉树中序遍历 
void BTreeInOrder(BTNode* root)
{
	if (root == NULL){
		return ;
	}
	
	BTreeInOrder(root->left);
    printf("%c ", root->data);
	BTreeInOrder(root->right);
}

BTNode* CreatTree(char *arr,int*i)
{
    if (arr[*i] == '#'){
        (*i)++;
		return NULL;
	}
    
    BTNode* newnode=(BTNode*)malloc(sizeof(BTNode));
    
    newnode->data=arr[(*i)++];//i必须取地址
    newnode->left=CreatTree(arr,i);//递归构建左子树
    newnode->right=CreatTree(arr,i);//递归构建右子树
    
    return newnode;
}

int main()
{
    char arr[100];
    scanf("%s",arr);
    
    int i=0;
    BTNode* root=CreatTree(arr,&i);
    BTreeInOrder(root);
    return 0;
}

100 相同的树

leetcode：100. 相同的树

题目要求很简单，给定两颗树的根节点，要求我们判断这两棵树是否相同

如果两棵树都为空，树相同
如果其中一个为空，另外一个不为空，树不同
如果两个都不为空，但是节点值不相同，树不同
然后再递归判断左子树和右子树，将它们的结果与&&在一起，其中一个为假，返回假

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p==NULL&&q==NULL)//比较是否两个节点都为空，都为空是真
        return true;
    
    if(p==NULL||q==NULL)//如果有一个为空，另外一个非空，即为假
        return false;

    if(p->val!=q->val)//都不是空，判断val的值是否相等
        return false;
    
    //递归判断左子树和右子树是否相等
    return isSameTree(p->left,q->left)
        && isSameTree(p->right,q->right);
}

这里顺便给出C++代码，基本一模一样

class Solution {
    // 两棵树按相同的方式进行遍历，就能判断出来
    bool _isSameTree(TreeNode* p, TreeNode* q) {
        // 两个都为空，相同
        if (p == nullptr && q == nullptr) {
            return true;
        }
        // 有一个为空，不相同
        if (p == nullptr && q != nullptr) {
            return false;
        }
        if (p != nullptr && q == nullptr) {
            return false;
        }
        // 值不相同
        if (p->val != q->val) {
            return false;
        }
        // 同时递归判断左右子树
        bool left = _isSameTree(p->left, q->left);
        bool right = _isSameTree(p->right, q->right);
        return left && right; // 左右子树都相同才是同一棵树
    }

public:
    bool isSameTree(TreeNode* p, TreeNode* q) { return _isSameTree(p, q); }
};

学会这道题后，后面一些题目其实只需要把它的代码改一改就能用了😂

什么？你不信？那就看看下面这道题！

101 对称二叉树

leetcode：101. 对称二叉树

题目要求很简单哈，判断是不是两边对称的树。这和判断树相等有什么区别呢？不就是把左右子树的判断改一下就行了嘛？

根节点的左子树的左侧和根节点的右子树的右侧相同，即为对称。

直接调用上一题的代码！注意最后的return值，是p的左和q的右进行判断

bool _isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p==NULL&&q==NULL)//比较是否两个节点都为空，都为空是真
        return true;
    
    if(p==NULL||q==NULL)//如果有一个为空，另外一个非空，即为假
        return false;

    if(p->val!=q->val)//都不是空，判断val的值是否相等
        return false;
    
    // 递归判断左子树和右子树是否对称相等
    return _isSameTree(p->left,q->right)
        && _isSameTree(p->right,q->left);
}

bool isSymmetric(struct TreeNode* root){
    return _isSameTree(root->left,root->right);
}

使用迭代法也能解决这道题目。迭代法的思路有点类似层序遍历，但是并不同！

使用队列存放节点，将根节点的左子树和右子树入队列
开始循环
取出队列的两个节点（根节点的左子树和右子树），将左子树的左侧和右子树的右侧入队列，将左子树的右侧和右子树的左侧入队列；
此时队列中的四个数值就是依照对称需要判断的节点值来排列的，在下一层循环的时候，只需要判断取出队列的头部两个节点的值是否相等就行了。
当取出的两个节点有一个为空，或者都不为空但节点值不同时，即不符合对称的条件。
注意，两个节点都为空是符合条件的。

C++代码如下

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr){
            return true;
        }
        queue<TreeNode*> que;
        que.push(root->left);
        que.push(root->right);

        while(!que.empty())
        {
            // 这里左右的顺序要和上面根节点插入左右的顺序一致
            TreeNode* left = que.front();
            que.pop();
            TreeNode* right = que.front();
            que.pop();
            if(left == nullptr && right == nullptr){
                continue; // 两个都是空，符合条件，跳过
            }
            // 有一个不为空，或者值不同，都是错误的
            if((left == nullptr || right == nullptr) || (left->val != right->val))
            {
                return false;
            }
            // 对称插入队列
            que.push(left->left);
            que.push(right->right);
            que.push(left->right);
            que.push(right->left);
        }
        return true;
    }   
};

572 另外一棵树的子树

leetcode：572. 另一棵树的子树

这道题我们要判断一颗树是否为另外一棵树的子树，和判断一个字符串是不是另外一个字符串的子串很相似

其实只需要递归判断每一个节点的左右子树是否和subRoot相同就可以了！

bool _isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p==NULL&&q==NULL)//比较是否两个节点都为空，都为空是真
        return true;
    
    if(p==NULL||q==NULL)//如果有一个为空，另外一个非空，即为假
        return false;

    if(p->val!=q->val)//都不是空，判断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&&subRoot==NULL)
    //     return true;
    // if(root!=NULL&&subRoot==NULL)
    //     return true;
    // 让isSametree函数来比较这俩个

    if(root==NULL)
        return false;

    if(_isSameTree(root,subRoot))
        return true;

    //只要左右有一个是返回真，那就是子树
    return isSubtree(root->left,subRoot)
        || isSubtree(root->right,subRoot);
}

是不是爽起来了？再来一道！

102 层序遍历

https://leetcode.cn/problems/binary-tree-level-order-traversal/

这道题在之前的博客中已经讲解过，为了方便后序写层序遍历的类型题目，将层序遍历最基本的代码贴在这里。

根节点入队列
队列不为空，开始遍历；
记录当前队列长度（本层节点数量），出对头节点，将值插入数组，并将该节点的左右子树入队列；
一层节点遍历完毕后，将这一层的数组插入返回值二维数组中；
依照以上步骤，直到最后一层（队列为空）；

代码如下。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> retV;
        if(root == nullptr){
            return retV;
        }
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            vector<int> tempV;
            for(int i = 0;i < size;i++)
            {
                TreeNode* front = que.front();
                que.pop();
                tempV.push_back(front->val);
                if(front->left != nullptr){
                    que.push(front->left);
                }
                if(front->right != nullptr){
                    que.push(front->right);
                }
            }
            retV.push_back(tempV); // 一层结束
        }
        return retV;
    }
};

107 层序遍历Ⅱ

https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/

这道题是上一道题的逆置，要求我们从最底层往上返回节点的数组。只需要将上题的返回数组逆置一下就OK了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
         vector<vector<int>> retV;
        if(root == nullptr){
            return retV;
        }
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            vector<int> tempV;
            for(int i = 0;i < size;i++)
            {
                TreeNode* front = que.front();
                que.pop();
                tempV.push_back(front->val);
                if(front->left != nullptr){
                    que.push(front->left);
                }
                if(front->right != nullptr){
                    que.push(front->right);
                }
            }
            retV.push_back(tempV); // 一层结束
        }
        // 逆置返回值数组即可
        reverse(retV.begin(),retV.end());
        return retV;
    }
};

199 二叉树的右视图

https://leetcode.cn/problems/binary-tree-right-side-view/description/

题目要求我们假设自己是从右侧观察一颗二叉树，返回能从右侧观察到的节点。

1
2
3

    5
  4   6
1   2

比如这棵树，从右侧可以观察到的节点是[5,6,2]，题目要求返回的就是这个节点组成的数组。

思路还是层序遍历，这一次不需要把每个节点都入数组了，只需要遍历到每个层的末尾（循环到size-1的位置），将这个节点插入数组就行了。

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> retV;
        if(root == nullptr){
            return retV;
        }
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            for(int i = 0;i < size;i++)
            {
                TreeNode* front = que.front();
                que.pop();
                // 每一层的末尾才插入数组
                if(i == size-1){
                    retV.push_back(front->val);
                }

                if(front->left != nullptr){
                    que.push(front->left);
                }
                if(front->right != nullptr){
                    que.push(front->right);
                }
            }
        }
        return retV;
    }
};

637 二叉树的层平均值

https://leetcode.cn/problems/average-of-levels-in-binary-tree/description/

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10^(-5) 以内的答案可以被接受。

这道题简单，把每一层的节点都加起来，然后除以节点数量求平均就可以了。

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> retV;
        if(root == nullptr){
            return retV;
        }
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            double sum = 0;
            for(int i = 0;i < size;i++)
            {
                TreeNode* front = que.front();
                que.pop();
                // 求和
                sum += front->val;

                if(front->left != nullptr){
                    que.push(front->left);
                }
                if(front->right != nullptr){
                    que.push(front->right);
                }
            }
            // 一层结束。计算平均
            retV.push_back(sum/static_cast<double>(size*1.0));
        }
        return retV;
    }
};

226 翻转二叉树

leetcode：226. 翻转二叉树

思路

这道题的思路如下哈！

如果是空树，不需要翻转，直接return；
如果非空，就把该节点的左右子树交换（这里不需要担心交换后找不到子树的问题，因为并没有把子树删除或者丢掉）
不需要单独判断空的子树，一并交换就可以；
当根节点为空的时候，return；

前序遍历实现

啪的一下很快哈，代码就写出来了！

void _invertTree(struct TreeNode* root)
{
    if(root==NULL)//设置退出条件，如果根节点为空就返回
        return;

    //让另外两个值来接收原本的左右节点
    struct TreeNode* left=root->left;
    struct TreeNode* right=root->right;

    //更改左右节点
    root->right=left;
    root->left=right;

    //递归子树
    _invertTree(root->left);
    _invertTree(root->right);
}

struct TreeNode* invertTree(struct TreeNode* root){
    if(root==NULL)//判断空树
        return NULL;

    _invertTree(root);
    
    return root;
}

使用迭代（循环）的方式进行前序遍历，也可以完成本题

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) {
	        return root;
	    }
	    
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();              // 中
            st.pop();
            swap(node->left, node->right); // 交换
            if(node->right) st.push(node->right);   // 右
            if(node->left) st.push(node->left);     // 左
        }
        return root;
    }
};

层序遍历实现

使用层序遍历，思路还是一样的，层序遍历在出队列头部节点的时候，会将左右子树插入队列。只需要在插入之前，将队列头部节点的左右子树指针交换位置，即可。

注意：不能通过交换左右子树入队列的顺序实现，这样虽然遍历下一层的顺序改变了，但是上一层的节点左右子树的指针并没有被交换，还是原来的顺序，不符合题目要求。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr){
            return root;
        }
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty())
        {
            TreeNode* front = que.front();
            que.pop();
            swap(front->left,front->right);

            // 虽然这里可以不用写不等于空，但是写上可读性更好。
            if(front->left != nullptr){
                que.push(front->left);
            }
            if(front->right != nullptr){
                que.push(front->right);
            }

        }
        return root;
    }
};

429 N叉树层序遍历

https://leetcode.cn/problems/n-ary-tree-level-order-traversal/

基于二叉树层序遍历的代码，修改一下就是多叉树了。

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> retV;
        if(root == nullptr){
            return retV;
        }
        queue<Node*> que;
        que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            vector<int> tempV;
            for(int j = 0; j < size ; j++){
                Node* temp = que.front();
                que.pop();
                tempV.push_back(temp->val);
                for(int i =0;i<temp->children.size();i++)
                {
                    que.push(temp->children[i]);
                }
            }
            retV.push_back(tempV);
        }
        return retV;
    }
};

515 在每层中找最大值

https://leetcode.cn/problems/find-largest-value-in-each-tree-row/

还是层序遍历思路的题目，遍历一层的时候维护一个最大值就可以了。

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> retV;
        if(root == nullptr){
            return retV;
        }
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            int maxNum = INT32_MIN;
            for(int i =0;i< size;i++)
            {
                TreeNode* temp = que.front();
                que.pop();
                maxNum = max(maxNum,temp->val);
                
                if(temp->left != nullptr){
                    que.push(temp->left);
                }
                if(temp->right != nullptr){
                    que.push(temp->right);
                }
            }
            retV.push_back(maxNum);
        }
        return retV;
    }
};

116 填充每个节点的下一个右侧节点指针

https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/description/

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

还是层序遍历的思路，遍历每一层的时候，将前一个节点的right设置为当前节点。

因为题目提到了node节点的next指针初始化都为nullptr，所以不需要我们手动操作每层最后一个节点的nullptr。

class Solution {
public:
    Node* connect(Node* root) {
        if(root == nullptr){
            return root;
        }
        queue<Node*> que;
        que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            Node* prevNode = nullptr;
            Node* node = nullptr; // 始终指向当前节点
            for(int i =0; i< size;i++)
            {
                // 每层第一个节点，设置前一个节点的值
                if(i == 0){
                    prevNode = que.front(); // 前一个节点
                    que.pop();
                    node = prevNode; // 当前节点
                }
                else // 非第一个
                {
                    node = que.front(); // 当前节点
                    que.pop();
                    prevNode->next = node;
                    prevNode = prevNode->next; // 更新前一个节点为当前节点
                }

                // 插入后续节点
                if(node->left != nullptr){
                    que.push(node->left);
                }
                if(node->right != nullptr){
                    que.push(node->right);
                }
            }
        }
        return root;
    }
};

117 填充每个节点的下一个右侧节点指针Ⅱ

https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/description/

上题说的是完全二叉树，这道题是普通二叉树。不过我们写的层序遍历代码本来就是通用的，所以直接复制代码过来就行了，什么都不需要改。

class Solution {
public:
    Node* connect(Node* root) {
        if(root == nullptr){
            return root;
        }
        queue<Node*> que;
        que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            Node* prevNode = nullptr;
            Node* node = nullptr; // 始终指向当前节点
            for(int i =0; i< size;i++)
            {
                // 每层第一个节点，设置前一个节点的值
                if(i == 0){
                    prevNode = que.front(); // 前一个节点
                    que.pop();
                    node = prevNode; // 当前节点
                }
                else // 非第一个
                {
                    node = que.front(); // 当前节点
                    que.pop();
                    prevNode->next = node;
                    prevNode = prevNode->next; // 更新前一个节点为当前节点
                }

                // 插入后续节点
                if(node->left != nullptr){
                    que.push(node->left);
                }
                if(node->right != nullptr){
                    que.push(node->right);
                }
            }
        }
        return root;
    }
};

104 二叉树最大深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

这道题在链式二叉树的博客中讲解过递归版本。注意二叉树深度的定义：二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

// 二叉树深度，即一共有几层
int BTreeDepth(BTNode* root)
{
	if (root == NULL) {
		return 0;
	}
	// 递归遍历左右子树
	int left = BTreeDepth(root->left);
	int right = BTreeDepth(root->right);
	// 返回左右子树层数高的那一个，加一代表当前层，因为空指针是0
	return left > right ? left + 1 : right + 1;
}

使用层序遍历也能解决这个问题，遍历到每一层都让深度计数器加一就行了。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int retDepth = 0;
        if(root == nullptr){
            return retDepth;
        }
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            retDepth++; // 层数加一
            for(int i =0;i< size;i++)
            {
                TreeNode* temp = que.front();
                que.pop();
                
                if(temp->left != nullptr){
                    que.push(temp->left);
                }
                if(temp->right != nullptr){
                    que.push(temp->right);
                }
            }
        }
        return retDepth;
    }
};

下面是代码随想录上的递归思路。使用“回溯”的思想，将每一层的depth送给下一层，然后在每一层开始的时候判断当前深度是否大于存放的深度，并进行更新。

class solution {
public:
    int result;
    void getdepth(TreeNode* node, int depth) {
        result = depth > result ? depth : result; // 中
        if (node->left == NULL && node->right == NULL) return ;
        if (node->left) { // 左
            getdepth(node->left, depth + 1);
        }
        if (node->right) { // 右
            getdepth(node->right, depth + 1);
        }
        return ;
    }
    int maxDepth(TreeNode* root) {
        result = 0;
        if (root == 0) return result;
        getdepth(root, 1);
        return result;
    }
};

114 二叉树的最小深度

https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/

二叉树的最小深度：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

以下面的二叉树为例，它的最小深度是从1到节点3，因为3才是第一个叶子节点，而1并不是叶子节点（没有左右子树的节点才是叶子节点）

代码如下

class Solution {
public:
    int minDepth(TreeNode* root) {
        int retDepth = 0;
        if(root == nullptr){
            return retDepth;
        }
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            retDepth++; // 层数加一
            for(int i =0;i< size;i++)
            {
                TreeNode* temp = que.front();
                que.pop();
                
                if(temp->left != nullptr){
                    que.push(temp->left);
                }
                if(temp->right != nullptr){
                    que.push(temp->right);
                }
                // 遇到叶子节点，说明就是最小深度，直接返回
                if(temp->left == nullptr && temp->right == nullptr){
                    return retDepth;
                }
            }
        }
        return retDepth;
    }
};

如果使用递归的方式，代码如下

class Solution {
public:
    int getDepth(TreeNode* node) {
        if (node == NULL) {
            return 0;
        }
        int leftDepth = getDepth(node->left);           // 左
        int rightDepth = getDepth(node->right);         // 右
                                                        // 中
        // 当一个左子树为空，右不为空，这时并不是最低点
        if (node->left == NULL && node->right != NULL) { 
            return 1 + rightDepth;
        }   
        // 当一个右子树为空，左不为空，这时并不是最低点
        if (node->left != NULL && node->right == NULL) { 
            return 1 + leftDepth;
        }
        // 此时是叶子节点，返回当前的最小高度（即深度）
        int result = 1 + min(leftDepth, rightDepth);
        return result;
    }

    int minDepth(TreeNode* root) {
        return getDepth(root);
    }
};

222 完全二叉树的节点数量

https://leetcode.cn/problems/count-complete-tree-nodes/description/

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1 ~ (2^h) 个节点。

先按普通二叉树来计算节点的数量，使用层序遍历的思路

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root == nullptr){
            return 0;
        }
        queue<TreeNode*> que;
        que.push(root);
        int count = 0;
        while(!que.empty())
        {
            int size = que.size();
            for(int i =0;i<size;i++)
            {
                TreeNode* front = que.front();
                que.pop();
                count++; 
                if(front->left != nullptr){
                    que.push(front->left);
                }
                if(front->right != nullptr){
                    que.push(front->right);
                }
            }
        }
        return count;
    }
};

使用递归遍历也能计算节点数量

class Solution {
public:
    int _countNodes(TreeNode* root)
    {
        if(root == nullptr){
            return 0;
        }

        int left = _countNodes(root->left);
        int right = _countNodes(root->right);
        return 1 + left + right;
    }

    int countNodes(TreeNode* root) {
        return _countNodes(root);
    }
};

但是上面这两个思路都是对任何二叉树都适用的，但本题直接说明了是完全二叉树。如果用通用的思路来解题，在面试的时候可能会扣分。我们需要用上完全二叉树的特性。

首先要知道满二叉树的节点数量为2^k - 1，k是二叉树的层数。在完全二叉树中，会有多个满二叉树。所以可以将思路转变为，正常计算非满二叉树的节点数量，但如果是满二叉树，获取层数后直接用公式计算节点数量，再二者相加。

计算满二叉树的层数比较简单，只需要从根节点往左侧、往右侧遍历，计算两侧的节点数量。最后对比左侧右侧节点数量，不同则不是满二叉树。

因为题目已经说明了这棵树是完全二叉树，所以不会出现下面这种两侧节点数量一致，但中间缺少节点不符合完全二叉树/满二叉树条件的情况。

C++代码如下，来自代码随想录。这里层数被初始化为0，这样在后续使用(2 << leftDepth)的时候，其实就相当于计算2的leftDepth+1次方。

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) {
            return 0; 
        }
        // 开始根据左深度和右深度是否相同来判断该子树是不是满二叉树
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
        while (left) {  // 求左子树深度
            left = left->left;
            leftDepth++;
        }
        while (right) { // 求右子树深度
            right = right->right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，返回满足满二叉树的子树节点数量
        }
        // 后序遍历
        int leftTreeNum = countNodes(root->left);       // 左
        int rightTreeNum = countNodes(root->right);     // 右
        int result = leftTreeNum + rightTreeNum + 1;    // 中
        return result;
    }
};

110 平衡二叉树

https://leetcode.cn/problems/balanced-binary-tree/

这里涉及到高阶数据结构中平衡二叉树的概念，如果你没有了解过，可以移步这篇博客；

简而言之，平衡二叉树是节点的左右子树高度相差不超过1的树。这样能保证树的左右两侧节点层数基本一致，方便实现搜索二叉树。

对于本题而言，我们可以将思路改为计算每个节点左右两侧的树的高度。当高度相差超过1的时候，直接返回错误。这里可以用int来作为递归函数的返回值，用-1代表不符合平衡二叉树的条件。

题目给出树的节点数量 [0, 5000] ，最大的层数也就5000，用int是足够存放的。

C++代码如下，使用后序遍历的思想来递归处理。

class Solution {
public:
    int _isBalanced(TreeNode* root){
        if(root == nullptr){
            return 0;
        }
        // 使用后续遍历，如果有一个不符合预期就提前返回
        int left = _isBalanced(root->left);
        if(left == -1){
            return -1;
        }
        int right = _isBalanced(root->right);
        if(right == -1){
            return -1;
        }
        // 都不是负一，计算节点高度插值
        if(abs(right -left)>1){
            return -1;// 超过1了不符合
        }
        else{
            return 1 + max(right,left); // 返回高的那一个作为当前树的高度
        }
    }

    bool isBalanced(TreeNode* root) {
        return _isBalanced(root) == -1 ? false : true;
    }
};

257 二叉树的所有路径

https://leetcode.cn/problems/binary-tree-paths/

思路是使用前序遍历，将当前节点的值转为字符串插入到数组中，并插入一个->字符串；递归的末尾条件分两个

叶子节点，将当前节点的值插入，不需要额外插入->字符串；
空节点，直接返回

递归函数的传参如下，其中string变量不能传引用，因为这样的话，下一层的修改就会影响上层，上层还需要做删除下一层的元素的操作，很麻烦。vector<string>& retV变量需要传引用，因为它包含了所有路径字符串，作为返回值。

1	void binaryTreePaths(TreeNode* root,string curStr,vector<string>& retV)

下面的代码中有一个错误的思路，如果遇到空节点就将字符串插入到数组，对于有一个子树的非叶子节点（此时它的左侧或者右侧是空的），就会多插入一个无效的路径，因为此时这个节点并非叶子节点。

正确的处理办法是到叶子节点了再插入数组，遇到空节点直接返回，不需要做任何处理。

class Solution {
public:
    // 字符串不能传引用，不然下层的更改会影响上层
    void binaryTreePaths(TreeNode* root,string curStr,vector<string>& retV)
    {
        // // 到空节点了就插入到数组中
        // if(root == nullptr){
        //     // 删除多余的->
        //     retV.push_back(curStr.substr(0,curStr.size()-2));
        //     return;
        // }

        // 上面的思路错误，如果某个节点有左子树或右子树，此时就会多插入一个无效的路径
        // 正确思路是空节点不处理
        if(root == nullptr){
            return ;
        }
        // 到叶子节点了就直接插入到数组中
        if(root->left == nullptr && root->right == nullptr){
            curStr +=  to_string(root->val);
            retV.push_back(curStr); // 不需要删除多余的->
            return ;
        }

        // 前序遍历
        curStr += to_string(root->val);
        curStr += "->";
        binaryTreePaths(root->left,curStr,retV);
        binaryTreePaths(root->right,curStr,retV);
    }


    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> retV;
        binaryTreePaths(root,"",retV);
        return retV;
    }
};

也可以使用迭代法，就是利用前序遍历的迭代思路将代码从递归改成迭代。

这里需要用到第二个栈，一个栈用来存放遍历的节点，另外一个栈用来存放当前遍历到的节点的上一层的字符串。

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> retV;
        if(root == nullptr){
            return retV;
        }

        stack<TreeNode*> stNode; // 存放节点
        stack<string> stStr; // 存放上一层的字符串
        stNode.push(root);
        // stStr.push(to_string(root->val));
        stStr.push(""); // 这里一定要插入空字符串而不是根节点的值

        while(!stNode.empty())
        {
            // 前序遍历
            TreeNode* curNode = stNode.top(); // 中
            // cout << curNode->val << endl;
            stNode.pop();
            string curStr = stStr.top();
            stStr.pop();
            // 遇到叶子节点，插入值然后返回
            if(curNode->left == nullptr && curNode->right == nullptr){
                // curStr += "->";
                curStr += to_string(curNode->val);
                retV.push_back(curStr);
                continue;
            }

            // 左
            if(curNode->left != nullptr){
                stNode.push(curNode->left);
                stStr.push(curStr  + to_string(curNode->val)+ "->");
            }
            // 右
            if(curNode->right != nullptr){
                stNode.push(curNode->right);
                stStr.push(curStr  + to_string(curNode->val)+ "->");
            }
        }
        return retV;
    }
};

404 左叶子之和

https://leetcode.cn/problems/sum-of-left-leaves/description/

给定二叉树的根节点 root ，返回所有左叶子之和。

这道题我本来的思路是使用层序遍历，除去根节点外，每一层的第一个就是左叶子的可能节点。注意是可能，还需要判断这个节点到底是不是叶子节点。如果是就将其加入sum中。

但是这个思路是错的，因为每一层不一定有左侧叶子节点，第一个节点可能是右子树，不符合题目条件。

正确的办法是用递归，顺序算是中序遍历，当遇到叶子节点和空节点的时候，返回0，当遇到当前节点的左侧节点是叶子节点的时候，返回这个节点的值。

因为左侧节点不能通过当前节点来判断出来，必须要用父亲节点才能判断，所以“中序”就是在通过父亲节点判断左侧节点是不是叶子节点。

class Solution {
public:
    int _sumOfLeftLeaves(TreeNode* root)
    {
        // 根节点为空，跳过
        if(root == nullptr){
            return 0;
        }
        // 叶子节点，跳过（因为左侧叶子节点不存在，值视作为0）
        if(root->left == nullptr && root->right == nullptr){
            return 0;
        }
        // 遍历左侧
        int left = _sumOfLeftLeaves(root->left);
        // 判断左侧是否为叶子节点，如果是需要进行修正（上一行的递归会跳过叶子节点的情况）
        if(root->left && root->left->left == nullptr && root->left->right==nullptr)
        {
            left = root->left->val; // 左侧叶子节点的值
        }
        // 遍历右侧
        int right = _sumOfLeftLeaves(root->right);

        return right + left;
    }

    int sumOfLeftLeaves(TreeNode* root) {
        
        return _sumOfLeftLeaves(root);
    }
};

你也可以把代码按下面的方式写，会更好理解一些。当判断出当前左子树是叶子节点，就直接赋值，不是叶子节点才去遍历。

class Solution {
public:
    int _sumOfLeftLeaves(TreeNode* root)
    {
        // 根节点为空，跳过
        if(root == nullptr){
            return 0;
        }
        // 叶子节点，跳过（因为左侧叶子节点不存在，值视作为0）
        if(root->left == nullptr && root->right == nullptr){
            return 0;
        }
        int left = 0;
        // 判断左侧是否为叶子节点
        if(root->left && root->left->left == nullptr && root->left->right==nullptr)
        {
            left = root->left->val; // 左侧叶子节点的值
        }
        else
        {
            left = _sumOfLeftLeaves(root->left);// 遍历左侧
        }
        
        // 遍历右侧
        int right = _sumOfLeftLeaves(root->right);

        return right + left;
    }

    int sumOfLeftLeaves(TreeNode* root) {
        return _sumOfLeftLeaves(root);
    }
};

使用迭代也是借用遍历的思路，都是在父节点判断左子树是否为叶子节点。下面的代码来自代码随想录。

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        stack<TreeNode*> st;
        if (root == NULL) return 0;
        st.push(root);
        int result = 0;
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
                result += node->left->val;
            }
            if (node->right) st.push(node->right);
            if (node->left) st.push(node->left);
        }
        return result;
    }
};

513 找树左下角的值

https://leetcode.cn/problems/find-bottom-left-tree-value/

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层最左边 节点的值。

假设二叉树中至少有一个节点。

这道题用上题层序遍历的思路才是对的，利用层序遍历走到最底层，将这一层最左侧的节点返回。但是这里会涉及到一个问题，我们怎么知道自己走到最后一层了呢？

实际上，并不需要去特殊判断，只需要将层序遍历每一层的第一个节点的值设置为返回值，这样层序遍历结束后，最后被设置的值就是题目需要求的节点。

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        if(root == nullptr)
        {
            return 0;
        }
        queue<TreeNode*> que;
        que.push(root);
        int ret = 0;
        while(!que.empty())
        {
            int size = que.size();
            for(int i =0;i<size;i++)
            {
                TreeNode* front = que.front();
                que.pop();
                if(i == 0){
                    ret = front->val;
                }
                if(front->left != nullptr){
                    que.push(front->left);
                }
                if(front->right != nullptr){
                    que.push(front->right);
                }
            }
        }
        return ret;
    }   
};

递归法使用前序遍历的思想，使用一个变量来记录当前深度，另外一个变量记录最深处左侧节点的值。这里的代码和上文104二叉树的最大深度题目中的思路相似。

class Solution {
public:
    int maxDepth = -1; // 最大深度
    int result = 0; // 左侧节点值

    void getMaxDepthLeftNode(TreeNode* root,int depth)
    {
        // 叶子节点
        if(root->right == nullptr && root->left == nullptr)
        {
            if(depth > maxDepth){
                maxDepth = max(maxDepth,depth);
                result = root->val; // 存放叶子节点的值
                return;
            }
        }
        // 如果左侧不为空，往左侧递归
        if(root->left != nullptr){
            getMaxDepthLeftNode(root->left,depth+1); // 这里深度加一就相当于加上当前节点
        }
        // 往右侧递归
        if(root->right != nullptr){
            getMaxDepthLeftNode(root->right,depth+1);
        }
        return;
    }

    int findBottomLeftValue(TreeNode* root) {
        if(root == nullptr){
            return 0;
        }
        getMaxDepthLeftNode(root,0);
        return result;
    }
};

112 路径总和

https://leetcode.cn/problems/path-sum/description/

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

这道题和257 二叉树的所有路径有些类似，不过那道题是需要将路径写入数组，这道题是需要判断有没有路径中节点值的和为指定数的情况。

递归函数中，传入目标值targetSum，当前值curSum（这里的当前值也是用了“回溯”的思想），为了避免错误修改目标值targetSum，将其设置为const变量。

1	bool frontTravelTree(TreeNode* root,const int targetSum, int curSum)

递归的思路如下

如果当前节点为空，直接返回false，不需要处理
如果当前节点非空，将当前节点的值加入curSum；
如果当前节点是叶子节点，判断当前的curSum是否等于targetSum，等于返回true；
往左侧和右侧递归，返回这两个递归结果的或；

注意，判断targetSum的时候一定要判断是不是叶子节点，我刚开始写的时候就忘记判断了，因为路径可能还没到叶子节点就已经等于targetSum了，但是这种情况不符合题目条件。

class Solution {
public:
    bool frontTravelTree(TreeNode* root,const int targetSum, int curSum)
    {
        if(root == nullptr){
            return false;
        }

        curSum += root->val;
        // 当前已经相等，且是叶子节点，返回
        if(targetSum == curSum && root->left == nullptr && root->right == nullptr){
            return true;
        }
        
        bool retLeft = frontTravelTree(root->left,targetSum,curSum);
        bool retRight = frontTravelTree(root->right,targetSum,curSum);
        return retLeft || retRight;
    }

    bool hasPathSum(TreeNode* root, int targetSum) {
        return frontTravelTree(root,targetSum,0);
    }
};

使用迭代，也是用前序遍历的思路，用栈来实现。这里的思路和257 二叉树的所有路径中也是一样的，需要用到两个栈，一个用来遍历节点，另外一个保存上一层遍历到的节点curSum。

注意，因为是前序遍历，且每一次都会让curSum加上当前节点的值，所以stSum这个栈在初始化的时候一定要插入0，而不是根节点的值（不然会二次加根节点的值，会出错）

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == nullptr){
            return false;
        }
        
        stack<TreeNode*> stNode; // 遍历节点
        stack<int> stSum; // 上一层遍历的求和结果
        
        stNode.push(root);
        stSum.push(0); // 这里一定要插入0而不是根节点的值

        while(!stNode.empty())
        {
            TreeNode* curNode = stNode.top();
            stNode.pop();
            int curSum = stSum.top();
            stSum.pop();
            
            curSum += curNode->val;
            // 如果是叶子节点，判断是否相等
            if(curNode->left == nullptr && curNode->right == nullptr && curSum == targetSum)
            {
                return true;
            }
            // 继续向下
            if(curNode->left != nullptr){
                stNode.push(curNode->left);
                stSum.push(curSum);
            }
            if(curNode->right != nullptr){
                stNode.push(curNode->right);
                stSum.push(curSum);
            }
        }
        return false;
    }
};

113 路径总和Ⅱ

113. 路径总和 II

上一题是让我们判断是否存在某一条路径，这题是需要返回所有符合条件的路径。

思路是使用前序遍历，用一个curSum记录当前遍历到的和，将当前值加入到这个和中并将当前值插入curV数组；

如果是叶子节点，则与targetSum对比，符合条件则将curV数组插入到返回值数组retV中。

class Solution {
    void _pathSum(TreeNode* root, const int targetSum,int curSum, vector<vector<int>>& retV,vector<int> curV) {
        // 空节点跳过
        if(root == nullptr){
            return ;
        }
        // 前序遍历
        curSum += root->val;
        curV.push_back(root->val);
        // 叶子节点，且值相等，插入
        if(root->left == nullptr && root->right == nullptr && curSum == targetSum){
            retV.push_back(curV);
            return;
        }
        // 左右递归
        _pathSum(root->left,targetSum,curSum,retV,curV);
        _pathSum(root->right,targetSum,curSum,retV,curV);
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> retV;
        if(root == nullptr){
            return retV;
        }

        _pathSum(root,targetSum,0,retV,vector<int>());
        return retV;
    }   
};

106 从中序与后序遍历序列构造二叉树

106 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

首先，要通过中序和后序遍历的概念知道如何从这两个数组中构造一棵树来。

后序的最后一个节点是根节点
确定根节点后，中序遍历中根节点左侧的是左子树，右侧的是右子树；
继续依照这个概念拆分后序遍历的数组，找到左右子树的根节点…

对于代码而言，重点就是将左右子树从中序和后序的数组中拆分开来，直到拆分到空节点。

数组大小为空，说明是空节点
数组大小不为空，从后序遍历中取出最后一个值作为根节点的值；
从中序遍历的数组中找到根节点所在位置，作为拆分的中位线；
将中序遍历的数组依照根节点所在位置拆分成左子数组和右子数组；
切割后序遍历的数组，依照左侧数组和右侧数组的长度和中序遍历拆分后的长度一致来处理（如果中序拆出来的左子树数组有3个元素，那么后序遍历中左子树的数组就是从前往后数的前3个元素）；
递归处理左侧和右侧的子树；

代码如下，主要需要注意的是拆分中序和后序数组时候迭代器的位置，这里的下标拆分范围如果搞不清楚可以打印出来多试试，记住思路是最重要的。

class Solution {
    TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 递归分治条件
        if(inorder.size() == 0 || postorder.size() == 0){
            return nullptr;
        }

        // 后序遍历的最后一个节点是根节点
        int val = postorder[postorder.size()-1];
        TreeNode* root = new TreeNode(val);

        // 在中序遍历数组中找到这个值，注意题目保证节点值不重复，所以能这么做。
        int i = 0; // 提前定义，后面要用
        for(i = 0;i<inorder.size();i++)
        {
            if(inorder[i] == val){
                break;
            }
        }

        // 拆中序数组，使用[0,i)区间
        vector<int> inorderLeft(inorder.begin(),inorder.begin()+i);
        // 下面这里是[i+1,end)区间，必须额外加一，否则不符合条件
        vector<int> inorderRight(inorder.begin()+i+1,inorder.end()); 


        // 拆后续数组，因为后续数组的大小肯定和中序一致，从前往后拆就分别对应中序的左数组和右数组了
        // 将后续遍历数组中的的最后一个值删掉，因为当前已经使用了
        postorder.resize(postorder.size()-1); 
        // 这里inorderLeft.size()理论上和i是相同的，所以用i也没问题
        // [0,inorderLeft.size())
        vector<int> postorderLeft(postorder.begin(),postorder.begin()+inorderLeft.size());
        // [inorderLeft.size(),end())
        vector<int> postorderRight(postorder.begin()+inorderLeft.size(),postorder.end());

        
        // 递归遍历
        TreeNode* left = _buildTree(inorderLeft,postorderLeft);
        TreeNode* right = _buildTree(inorderRight,postorderRight);
        // 链接
        root->left = left;
        root->right = right;
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size() == 0 || postorder.size() == 0){
            return nullptr;
        }
        return _buildTree(inorder,postorder);
    }
};

当然，上面的代码性能并不好，因为会有额外的空间复杂度消耗（每次递归都需要构建4个vector数组），我们可以将构建数组的操作改成用下标来标定区间。

代码如下，同样需要注意下标的区间，详见注释。

class Solution {
    TreeNode* _buildTree(const vector<int>& inorder,int inorderBegin,int inorderEnd,const vector<int>& postorder,int postorderBegin,int postorderEnd) {        
        if(inorderBegin>=inorderEnd || postorderBegin >= postorderEnd){
            return nullptr;
        }

        // 后序遍历的最后一个节点是根节点
        // int val = postorder[postorder.size()-1];
        int val = postorder[postorderEnd-1];
        TreeNode* root = new TreeNode(val);

        // 在中序遍历数组中找到这个值，注意题目保证节点值不重复，所以能这么做。
        int i = 0; // 提前定义，后面要用
        // for(i = 0;i<inorder.size();i++)
        for(i = inorderBegin;i<inorderEnd;i++)
        {
            if(inorder[i] == val){
                break;
            }
        }

        // 拆中序数组，使用[0,i)区间
        int inorderBeginLeft = inorderBegin;
        int inorderEndLeft = inorderBegin+(i-inorderBegin); // 如果直接加i是错误的，i已经是下标了，再加会超出范围

        // 下面这里是[i+1,end)区间，必须额外加一，否则不符合条件
        int inorderBeginRight = inorderBegin+(i-inorderBegin)+1; // 这里需要加一，是跳过被选中的中间节点
        int inorderEndRight = inorderEnd;

        // 拆后续数组，因为后续数组的大小肯定和中序一致，从前往后拆就分别对应中序的左数组和右数组了
        // [0,inorderLeft.size())
        int postorderBeginLeft = postorderBegin;
        int postorderEndLeft = postorderBegin + (i - inorderBegin);

        // [inorderLeft.size(),end())
        int postorderBeginRight = postorderBegin + (i - inorderBegin); // 这里不需要加一，因为中间没有多出来一个数
        int postorderEndRight = postorderEnd -1; // 排除最后一个节点

        // 递归遍历
        TreeNode* left = _buildTree(inorder,inorderBeginLeft,inorderEndLeft,postorder,postorderBeginLeft,postorderEndLeft);
        TreeNode* right = _buildTree(inorder,inorderBeginRight,inorderEndRight,postorder,postorderBeginRight,postorderEndRight);
        // 链接
        root->left = left;
        root->right = right;
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size() == 0 || postorder.size() == 0){
            return nullptr;
        }
        return _buildTree(inorder,0,inorder.size(),postorder,0,postorder.size());
    }
};

105 从前序和中序遍历构造二叉树

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

这道题和上一道题的思路基本一致，这里就不用构造vector的思路了，直接用下标的方式来处理。

前序遍历的第一个值是根节点
在中序遍历的数组中找到根节点的位置，根据该位置左右拆分数组
在前序遍历数组中，从第二位开始，根据中序遍历拆出来的两个数组的长度，拆分前序遍历的数组。
递归处理

在后序遍历的数组中，需要排除的是最后一位。在前序遍历的数组中，需要排除的是第一位。在拆分数组下标的地方体现出来。

class Solution {
    TreeNode* _buildTree(const vector<int>& preorder,int preorderBegin,int preorderEnd,const  vector<int>& inorder, int inorderBegin,int inorderEnd)
    {
        // 递归返回条件
        if(inorderBegin >= inorderEnd || preorderBegin >= preorderEnd){
            return nullptr;
        }
        // 前序遍历的第一个
        int val = preorder[preorderBegin];
        TreeNode* root = new TreeNode(val);

        // 在中序遍历数组中找
        int i =0;
        for(i = inorderBegin;i<inorderEnd;i++){
            if(inorder[i] == val){
                break;
            }
        }

        // 拆分中序遍历数组
        int offset = i-inorderBegin;
        // 左侧数组[inorderBegin,inorderBegin+offset)
        int inorderBeginLeft = inorderBegin;
        int inorderEndLeft = inorderBegin + offset;  // 这里不能直接加i，应该加i和开头的偏移量
        // 右侧数组[inorderBegin+offset+1,inorderEnd)
        int inorderBeginRight = inorderBegin + offset+1;
        int inorderEndRight = inorderEnd;

        // 拆分前序遍历数组
        // 左侧数组[preorderBegin+1,preorderBegin+1+offset)，开头需要加一跳过第一个值
        int preorderBeginLeft = preorderBegin+1;
        int preorderEndLeft = preorderBegin+1+offset;
        // 右侧数组[preorderBegin+1+offset,preorderEnd)
        int preorderBeginRight = preorderBegin+1+offset;
        int preorderEndRight = preorderEnd;

        // 递归遍历
        TreeNode* left = _buildTree(preorder,preorderBeginLeft,preorderEndLeft,inorder,inorderBeginLeft,inorderEndLeft);
        TreeNode* right = _buildTree(preorder,preorderBeginRight,preorderEndRight,inorder,inorderBeginRight,inorderEndRight);
        // 链接
        root->left = left;
        root->right = right;
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0 || inorder.size() == 0){
            return nullptr;
        }
        return _buildTree(preorder,0,preorder.size(),inorder,0,inorder.size());
    }
};

654 最大二叉树

654. 最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值左边的 子数组前缀上 构建左子树。
递归地在最大值右边的 子数组后缀上 构建右子树。

返回 nums 构建的最大二叉树 。

这道题和前面105/106这两道题的思路几乎完全一致，用前序遍历递归的思想，先找到最大值作为根节点，然后拆分左右区间（类似与105/106题目中拆分中序遍历数组的左右区间）。拆分区间后进行遍历构建左右子树就行了。

这里要注意递归的退出条件，因为begin/end选用的是左闭右开的选择，所以begin==end的情况也是无效的，所以begin>=end作为递归的退出条件。

class Solution {
    // 查找最大值，返回最大值的下标
    int searchMaxIndex(const vector<int>& nums,int begin,int end){
        int maxNum = nums[begin];
        int maxNumIndex = begin;
        for(int i = begin;i<end;i++)
        {
            if(nums[i] > maxNum){
                maxNum = nums[i];
                maxNumIndex = i;
            }
        }
        return maxNumIndex;
    }

    TreeNode* _constructMaximumBinaryTree(const vector<int>& nums,int begin,int end){
        // 本题采用左闭右开，所以begin==end是无效区间
        if(nums.size() == 0 || begin>=end){
            return nullptr;
        }
        // 找到最大值的下标
        int maxNumIndex = searchMaxIndex(nums,begin,end);
        TreeNode* root = new TreeNode(nums[maxNumIndex]);
        // 左右拆分
        int leftBegin = begin;
        int leftEnd = maxNumIndex; 

        int rightBegin = maxNumIndex+1; // 加一跳过当前选中节点
        int rightEnd = end;

        root->left = _constructMaximumBinaryTree(nums,leftBegin,leftEnd);
        root->right = _constructMaximumBinaryTree(nums,rightBegin,rightEnd);
        return root;
    }
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if(nums.size() == 0){
            return nullptr;
        }
        return _constructMaximumBinaryTree(nums,0,nums.size());
    }
};

617 合并二叉树

617. 合并二叉树

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

这道题其实就是遍历二叉树多了第二棵树而已，不需要想的太复杂

class Solution {
    TreeNode* _mergeTrees(TreeNode* root1, TreeNode* root2) {
        // 如果一棵树为空了，就直接返回另外一棵树来拼接
        if(root1 == nullptr){
            return root2;
        }
        if(root2 == nullptr){
            return root1;
        }
        // 借用root1加上值
        root1->val += root2->val;
        // 这里因为root1和root2的遍历顺序都是一样的，所以肯定能匹配上
        root1->left = _mergeTrees(root1->left,root2->left);
        root1->right = _mergeTrees(root1->right,root2->right);
        return root1;
    }
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        return _mergeTrees(root1,root2);
    }
};

使用迭代法的层序遍历思想也能解决这道题，需要将两棵树的根都插入队列中。在开始遍历之前，需要确定我们是用root1还是root2来构造最终的二叉树。

取出节点，值相加
如果两个节点的左侧都不为空，入队列（注意顺序要一致）
如果两个节点的右侧都不为空，入队列
如果r1的左侧节点为空，r2不为空，将r1的左侧链接为r2
如果r1的右侧节点为空，r2不为空，将r1的右侧链接为r2

代码如下

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        // 如果一棵树为空了，就直接返回另外一棵树来拼接
        if(root1 == nullptr){
            return root2;
        }
        if(root2 == nullptr){
            return root1;
        }
        // 到这里root1和2都不为空
        queue<TreeNode*> que;
        que.push(root1);
        que.push(root2);
        // 确定用root1来链接树
        while(!que.empty())
        {
            // 这里不需要多层序遍历的循环，因为root1和root2每一层节点个数不相同
            
            TreeNode* r1 = que.front();
            que.pop();
            TreeNode* r2 = que.front();
            que.pop();
            r1->val += r2->val;
            // 如果两个节点的左右子树都不空，则都插入数组
            if(r1->left != nullptr && r2->left != nullptr){
                que.push(r1->left);
                que.push(r2->left);
            }
            if(r1->right != nullptr && r2->right != nullptr){
                que.push(r1->right);
                que.push(r2->right);
            }
            // 如果r1的左侧为空，r2不为空，赋值
            if(r1->left == nullptr && r2->left != nullptr)
            {
                r1->left = r2->left;
            }
            if(r1->right == nullptr && r2->right != nullptr)
            {
                r1->right = r2->right;
            }
            
        }
        return root1;
    }
};

700 二叉搜索树中的搜索

700. 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

代码如下，其实就是最最基本的搜索二叉树的查找方式。搜索二叉树的左子树的值小于当前节点的值，右子树的值大于当前节点的值。

class Solution {
    TreeNode* _searchBST(TreeNode* root,const int val) {
        if(root == nullptr){
            return nullptr;
        }

        if(root->val == val){
            return root;
        }

        if(root->val > val){
            return _searchBST(root->left,val); // 左侧更小
        }
        else{
            return _searchBST(root->right,val); // 右侧更小
        }
    }
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root == nullptr){
            return nullptr;
        }
        return _searchBST(root,val);
    }
};

用循环也能实现，因为这里不涉及到前中后序遍历什么的，只是单纯找一个值，所以用不上队列或者栈

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        // 用循环也可以
        while(root != nullptr)
        {
            if(root->val == val){
                return root;
            }
            
            if(root->val > val)
            {
                root = root->left;
            }
            else
            {
                root = root->right;
            }
        }
        return nullptr;
    }
};

98 验证二层搜索树

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

注意：二叉搜索树中不能有重复节点，因为无法判断两个相同节点的区别。

这道题可以采用中序遍历的方式，构建一个二叉树的数组，并遍历判断这个数组是否有序（搜索二叉树的中序遍历肯定是有序的），代码如下

class Solution {
    void _inorderTravel(TreeNode* root,vector<int>& v)
    {
        if(root == nullptr){
            return ;
        }

        _inorderTravel(root->left,v);
        v.push_back(root->val);
        _inorderTravel(root->right,v);
    }
public:
    bool isValidBST(TreeNode* root) {
        // 本题保证root非空
        vector<int> v;
        _inorderTravel(root,v);
        for(int i =0;i<v.size()-1;i++){
            // 不能有重复节点，这里是大于等于
            if(v[i] >= v[i+1]){
                return false;
            }
        }
        return true;
    }
};

当然，不用额外的数组也能写出这道题。思路是用中序遍历，维护一个当前最大值（初始化为LONG_MIN），在中序部分判断当前节点是否小于这个最大值，如果小于等于，则说明当前节点之前有比当前节点更大或等于当前值的节点，这是不符合条件的，返回假。

其他情况返回真。

因为本题目保证了root是非空的，所以第一个root的判断返回false/true可以根据算法自行选择。

class Solution {
public:
    long maxNum = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if(root == nullptr){
            return true;
        }
        bool retLeft = isValidBST(root->left);

        if(root->val <= maxNum){
            return false;
        }
        else{
            maxNum = root->val;
        }
        
        bool retRight = isValidBST(root->right);

        return retLeft && retRight;
    }
};

这个算法还是会有一个问题，即二层搜索树中可能会存在本来就等于LONG_MIN的节点，此时会直接返回false，不符合预期。所以应该把maxNum初始化为二叉树中左下角的那个节点的值，来保证无论如何都可以遍历成功，避免我们选用的初始值对算法结果的影响。

class Solution {
public:
    TreeNode* prev = nullptr;
    bool isValidBST(TreeNode* root) {
        if(root == nullptr){
            return true;
        }
        bool retLeft = isValidBST(root->left);

        if(prev != nullptr && root->val <= prev->val){
            return false;
        }
        else{
            prev = root;
        }
        
        bool retRight = isValidBST(root->right);

        return retLeft && retRight;
    }
};

530 二叉搜索树的最小绝对差

530. 二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

因为题目给的是搜索二叉树，还是和前两题类似，利用中序遍历的有序序列，计算两个相邻节点之间的差值，差值的最小值只可能是在两个相邻节点之间。这就好比给你一个有序的单调递增的数组，让你返回这个数组中任意两个数的最小差值一样。

同样，可以用中序遍历将搜索二叉树转为数组再进行处理，具体代码参考上题（一模一样的转化再遍历），这里给出直接用中序遍历递归实现的的算法，思路是维护一个当前节点的前一个节点的指针，并依次计算两个相邻节点之间的差值。

class Solution {
public:
    int minDiff = INT_MAX;
    TreeNode* prev = nullptr;
    void _getMinimumDifference(TreeNode* root)
    {
        if(root == nullptr){
            return ;
        }
        // 遍历左侧
        _getMinimumDifference(root->left);

        // 计算差值
        if(prev != nullptr){
            minDiff = min(minDiff,root->val - prev->val);
        }
        // 所有情况都需要更新prev
        prev = root;
      
        // 遍历右侧
        _getMinimumDifference(root->right);
    }

    int getMinimumDifference(TreeNode* root) {
        _getMinimumDifference(root);
        return minDiff;
    }
};

使用迭代，利用中序遍历的迭代思路也能解决这道题，这里主要是要记住怎么使用栈进行中序遍历。

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        if(root == nullptr){
            return 0;
        }
        stack<TreeNode*> st;

        TreeNode* prev = nullptr;
        TreeNode* cur = root;
        int ret = INT_MAX; // 最小差值

        // 两个条件符合都不符合才停止循环
        while(cur != nullptr || !st.empty())
        {
            if(cur != nullptr){
                st.push(cur);
                cur = cur->left; // 左
            }
            else{ // 往左一直走到空了
                cur = st.top(); // 父亲节点
                st.pop();
                // 中序处理，计算最小值
                if(prev != nullptr){
                    ret = min(ret,cur->val - prev->val);
                }
                prev = cur;
                // 右
                cur = cur->right;
            }
        }
        return ret;
    }
};

501 二叉搜索树中的众数

501. 二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

这道题首先可以按任何二叉树来操作，即遍历整棵树，用map记录某个节点出现的频率，最终将出现频率最高的几个数取出来。

注意，这里不能一上来就直接用优先级队列，因为优先级队列是没有办法修改某个值的。可以用map统计完后再用优先级队列来排序。

class Solution {
    // 因为只是遍历统计，所以用什么顺序遍历都没有区别
    void inorderTravel(TreeNode* root,unordered_map<int,int>& countMap)
    {
        if(root == nullptr){
            return ;
        }
        inorderTravel(root->left,countMap);
        countMap[root->val]++;
        inorderTravel(root->right,countMap);
    }

    class MyCmp{
    public: // 别忘了设置为公有
        bool operator()(const pair<int,int>& p1, const pair<int,int>& p2){
            return p1.second < p2.second; // 使用小于建立大堆
        }
    };

public:
    vector<int> findMode(TreeNode* root) {
        vector<int> retV;
        if(root == nullptr){
            return retV;
        }
        unordered_map<int,int> countMap;
        inorderTravel(root,countMap);
        // 使用优先级队列来初始化值
        priority_queue<pair<int,int>,vector<pair<int,int>>,MyCmp> que(countMap.begin(),countMap.end());
        // 取出头部计数器相同的，插入数组
        auto curPair = que.top();
        que.pop();
        retV.push_back(curPair.first);
        // 只要队列不为空就继续操作
        while(!que.empty()){
            // 当当前计数和刚刚插入的一致，则继续插入
            if(curPair.second == que.top().second){
                curPair = que.top();
                que.pop();
                retV.push_back(curPair.first);
            }
            else
            {
                break; // 不符合条件，跳出
            }
        }
        return retV;
    }
};

不过本题是一个搜索二叉树，解题方法肯定不同。还是那个性质，搜索二叉树的中序遍历结果是有序的，那么我们就可以通过这个有序来遍历计算当前数字出现的频率。同样是维护一个prev指针指向上一个节点，并对连续相同的数进行计数。

当遇到第一个不相同的节点时，清空计数器，将上一个节点插入返回值数组，重新开始计数。如果新的这个数字的数量大于上一个数字，那么就将返回值数组清空（因为此时返回值数组中的元素是无效的），重新按这个新的count计算众数。

class Solution {
    int maxCount = -1; // 计数器肯定是正的，初始化为负数即可
    int count = 0; // 这里不能用count作为参数，因为每一层的修改对全局都是有效的
    TreeNode* prev = nullptr;
    
    void inordereTravelCount(TreeNode* root,vector<int>& retV)
    {
        if(root == nullptr){
            return;
        }
        // 左
        inordereTravelCount(root->left,retV);
        // 中，计数
        if(prev == nullptr)// 第一个节点
        {
            count = 1;
        }
        else if(prev->val == root->val) // 相同
        {
            count++;
        }
        else // 不相同，新的节点
        {
            count = 1;
        }
        prev = root;

        // 和当前记录最大值相同，插入        
        if(count == maxCount)
        {
            retV.push_back(root->val);
        }
        // 超过了最大记录，需要清空返回值数组
        else if(count > maxCount){
            maxCount = count;
            retV.clear();
            retV.push_back(root->val);
        }

        inordereTravelCount(root->right,retV);
    }

public:
    vector<int> findMode(TreeNode* root) {
        vector<int> retV;
        inordereTravelCount(root,retV);
        return retV;
    }
};

236 二叉树的最近公共祖先

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1

提示：

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

首先要明确，root也可以是自己的公共祖先，所以root等于p或者等于q的情况也是符合条件的。本题需要我们从左右子树中找到p和q，然后再往上返回它的最近公共祖先，即从树的底部往上遍历。后序遍历（左右中）就是符合这个条件的。

下图中，带序号的线代表后序遍历的顺序，长虚线代表每一次的返回值。

整体思路如下：

判断root是否等于q/p，或者root为空，此时返回root；
递归判断左侧和右侧，记录返回值
如果左侧和右侧返回值都不为空，则代表当前节点就是最近的公共祖先节点，返回root节点（当前节点）；
如果左侧和右侧有一个为空，则返回不为空的那一个；
如果左侧和右侧都为空，则返回空（代表当前节点的子树中没有找到q和p）；

代码如下

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // root也可以是它自己的祖先
        if(root == nullptr || root == p || root == q){
            return root;
        }
        // 用后序遍历的思路来处理，这样能找到当前节点的孩子里面有么有q或者p
        TreeNode* left = lowestCommonAncestor(root->left, p,  q);
        TreeNode* right = lowestCommonAncestor(root->right, p,  q);
        // 如果左右都不为空，则代表root就是最近的公共祖先
        if(left != nullptr && right != nullptr){
            return root;
        }
        
        // // // 如果两个都为空，代表没有找到，返回空
        // if(left == nullptr && right == nullptr){
        //     return nullptr;
        // }
        // // 如果有一个为空，则返回另外一个
        // if(left != nullptr && right == nullptr){
        //     return left;
        // }
        // if(left == nullptr && right != nullptr){
        //     return right;
        // }
        // return nullptr; // 这里的返回没有意义，因为不会走到这里来

        // 上面的三个判断可以精简成下面这个
        // 如果left为空且right也为空的时候，本来就需要返回nullptr，此时返回right也是一样的
        return left != nullptr ? left : right;
    }
};

235 二叉搜索树的最近公共祖先

235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

本题和上一题要求一致，但树是搜索二叉树。利用这个特性，给定q和p的公共祖先的值肯定在[q, p]范围区间之间（注意q和p没有说明谁更大，所以要判断q<cur< p和p<cur<q的两种情况），找公共祖先，只需要从上往下，找到第一个值符合这个区间范围的节点就可以了。

搜索二叉树的左侧小于当前节点，右侧大于当前节点；
从上往下遍历（用前序遍历），此时先处理的是中间节点，那么第一个找到的符合[q,p]区间的节点就是最近的公共祖先，此时往左还是往右都会错过；

如下所示，找1和8节点的公共祖先（即5），此时如果往左走到3，就会错过8的祖先，往右走到9，就会错过1的公共祖先

理解思路了，代码就不难写了，前序遍历的二叉搜索代码就可以了。因为这是搜索二叉树，不需要递归也能实现。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr){
            return nullptr;
        }
        TreeNode* cur = root;
        // 找到q和p中的最小值
        int min = q->val,max = p->val;
        if(min > max){
            min = max;
            max = q->val;
        }

        while(cur != nullptr)
        {
            // 符合条件
            if(cur->val >= min && cur->val <= max)
            {
                return cur;
            }
            // 如果大了，就往左走
            if(cur->val > max){
                cur = cur->left;
            }
            // 小了就往右边走
            if(cur->val < min){
                cur = cur->right;
            }
        }
        return nullptr;
    }
};

701 二叉搜索树中的插入操作

701. 二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回 任意有效的结果 。

这道题没有那么难，因为题目要求的是二叉搜索树，并不是平衡二叉搜索树，所以不存在需要翻转的情况。我们只需要找到这个新节点应该存放的位置，将其链接进去就行了。

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        TreeNode* newNode = new TreeNode(val);
        if(root == nullptr){
            return newNode;
        }
        TreeNode* cur = root;
        TreeNode* prev = root;
        while(cur != nullptr)
        {
            if(cur->val > val){
                prev = cur;
                cur = cur->left;
                continue;
            }
            if(cur->val < val){
                prev = cur;
                cur = cur->right;
                continue;
            }
        }
        // 走到对应位置了
        
        // 上一个节点肯定是叶子节点
        // 当前节点值更大，是左侧
        if(prev->val > val){
            prev->left = newNode;
        }
        // 当前节点值更小，所以是右侧
        if(prev->val < val){
            prev->right = newNode;
        }
        return root;
    }
};

450 删除二叉搜索树中的节点

450. 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

提示:

节点数的范围 [0, 104]
-105 <= Node.val <= 105
节点值唯一
root 是合法的二叉搜索树
-105 <= key <= 105

删除搜索二叉树中的节点需要判断当前的情况

没找到需要删除的节点，直接返回；
当前节点是叶子节点，将父节点的指针改成nullptr，delete该节点即可；
当前节点左侧节点为空，右侧不为空，将右侧节点记录，父节点的指针改成右侧节点，删除当前节点；
当前节点右侧节点为空，左侧不为空，将左侧节点记录，父节点的指针改成左侧节点，删除当前节点；
当前节点左侧右侧都不为空，将当前节点的左侧移动至右侧的最左节点，

这里最难处理的是最后一种情况，见下图，红色是要被删除的节点5，绿色是该节点的左子树，蓝色是该节点的右子树。我们需要将5节点的左子树3移动到它的右子树的最左侧节点（即移动到6的位置）链接上。

因为是二叉搜索树，所以不需要用递归，循环找节点就行了。

class Solution {
private:

    TreeNode* deleteOneNode(TreeNode* target) {
        if (target == nullptr) {
            return target;
        }
        // 右侧为空，无论如何都返回左侧
        if (target->right == nullptr) {
            return target->left;
        }
        // 右侧不为空，统一处理，找到右子树的最左侧节点，进行链接
        TreeNode* cur = target->right;
        while (cur->left != nullptr) {
            cur = cur->left;
        }
        cur->left = target->left;
        return target->right;
    }

public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) {
            return root;
        }
        TreeNode* cur = root;
        TreeNode* pre = nullptr; // 记录cur的父节点，用来删除cur
        while (cur != nullptr) {
            if (cur->val == key) {
                break;
            }

            pre = cur;
            if (cur->val > key) {
                cur = cur->left;
            } else {
                cur = cur->right;
            }
        }
        if (pre == nullptr) { // 如果搜索树只有头结点
            return deleteOneNode(cur);
        }
        // 判断删左孩子还是右孩子
        if (pre->left != nullptr && pre->left == cur) {
            pre->left = deleteOneNode(cur);
        }
        if (pre->right != nullptr && pre->right == cur) {
            pre->right = deleteOneNode(cur);
        }
        return root;
    }
};

669 修剪二叉搜索树

669. 修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

这里使用递归的方式来处理节点，通过返回值来将需要删除的节点排除掉。

空节点，返回（递归末端条件）；
如果当前节点小于目标区间，则往右侧找并返回（这就相当于删除了当前节点）；
如果当前节点大于目标区间，则往左侧找并返回（这就相当于删除了当前节点）；
如果当前节点符合目标区间，则递归遍历左子树和右子树，并重新赋值新的左子树和右子树；

其中最后一步是比较重要的，当前节点符合条件后，它的左侧和右侧可能会有不在区间内的节点，所以在递归遍历的同时，需要更新当前节点的左右子树指针，来接受递归后剔除了不符合条件节点的树。

主要是理解如何通过递归的返回值来巧妙的“删除”不符合条件的节点。以上图的树为例，给定区间[2,4]，需要删除的节点是0和1。过程如下

3符合条件，递归遍历左子树和右子树
右子树的4符合条件，递归遍历左子树和右子树（都为空，直接返回，相当于对4的节点没有做修改），最终返回4节点，赋值给3节点的right（也相当于没有修改）
左子树的0不符合条件（小于边界最小值），递归遍历右子树；
右子树的2符合条件，递归遍历左子树和右子树（2的右子树是空，直接返回）；
2的左子树1不符合条件（小于边界最小值），递归遍历右子树，此时1的右子树为空，相当于遍历1的这一次也是返回nullptr，并赋值给了2节点的right，相当于删除了节点1；
此时递归返回，2号节点往上返回（即遍历到0的那一次会返回2号节点），赋值给了3号节点的right，相当于删除了节点0。

代码如下

class Solution {
    TreeNode* _trimBST(TreeNode* root, const int low,const int high) {
        if(root == nullptr){
            return root;
        }
        // 注意题目给出的是闭区间，所以这里超出的情况不包括=的情况
        // 如果当前节点值不在区间内，则往右边/左边找是否有符合条件的
        // 如果有则会正常返回符合条件的节点（也相当于通过返回值把当前节点删掉了）
        if(root->val < low){
            return _trimBST(root->right,low,high);
        }
        if(root->val > high){
            return _trimBST(root->left,low,high);
        }

        // 当前root的值符合范围，递归左子树和右子树，剔除不符合条件的节点
        root->left = _trimBST(root->left,low,high);
        root->right = _trimBST(root->right,low,high);
        return root;
    }
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root == nullptr){
            return root;
        }
        return _trimBST(root,low,high);
    }
};

108 将有序数组转为二叉搜索树

108. 将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。

这道题其实没有想象中的那么难，因为题目给的数组是有序的（可以理解为本来就是一格二叉搜索树的中序遍历数组形式），我们只需要通过前序遍历加上拆分数组，最终构建出来的树肯定会是一个平衡的二叉搜索树。

在上文中的654 最大二叉树中已经使用了拆分数组构建树的方式，那道题是需要找到数组中的最大点。本题的平衡二叉搜索树需要找到有序数组的中间节点（即当前的中位数）作为根。

class Solution {
    TreeNode* _sortedArrayToBST(const vector<int>& nums,int left,int right) {
	    // 注意right是开区间，left=right的时候也无效
        if(left >= right){
            return nullptr;
        }
        int mid = left + ((right - left)/2); 
        
        // int mid = (right - left)/2; // 这样计算的结果是错误的，值可能会小于left，导致陷入死循环

        TreeNode* root = new TreeNode(nums[mid]);
        root->left = _sortedArrayToBST(nums,left,mid);
        root->right = _sortedArrayToBST(nums,mid+1,right);
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.size() == 0){
            return nullptr;
        }
        return _sortedArrayToBST(nums,0,nums.size());
    }
};

如果使用迭代法，需要三个队列，一个存放节点，一个存放左区间，一个存放右区间。以下代码来自代码随想录。

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.size() == 0) return nullptr;

        TreeNode* root = new TreeNode(0);   // 初始根节点
        queue<TreeNode*> nodeQue;           // 放遍历的节点
        queue<int> leftQue;                 // 保存左区间下标
        queue<int> rightQue;                // 保存右区间下标
        nodeQue.push(root);                 // 根节点入队列
        leftQue.push(0);                    // 0为左区间下标初始位置
        rightQue.push(nums.size() - 1);     // nums.size() - 1为右区间下标初始位置

        while (!nodeQue.empty()) {
            TreeNode* curNode = nodeQue.front();
            nodeQue.pop();
            int left = leftQue.front(); leftQue.pop();
            int right = rightQue.front(); rightQue.pop();
            int mid = left + ((right - left) / 2);

            curNode->val = nums[mid];       // 将mid对应的元素给中间节点

            if (left <= mid - 1) {          // 处理左区间
                curNode->left = new TreeNode(0);
                nodeQue.push(curNode->left);
                leftQue.push(left);
                rightQue.push(mid - 1);
            }

            if (right >= mid + 1) {         // 处理右区间
                curNode->right = new TreeNode(0);
                nodeQue.push(curNode->right);
                leftQue.push(mid + 1);
                rightQue.push(right);
            }
        }
        return root;
    }
};

538 把二叉搜索树转为累加树

538. 把二叉搜索树转换为累加树

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。

注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

题目要求的是将每个节点的值转为它和它右侧的节点的和。用数组可能更好理解一些，即将当前数组下标位置的值改为它和它右侧的节点的和。

所以可以从右侧往左侧遍历这个数组，记录一个求和值，并将当前数组的值加上这个求和值就行了。比如数组[15,24,30]的结果是[68,54,30]；

对于二叉树也是一样的，从右侧往左侧遍历，顺序是右中左，把中序遍历的代码改一下顺序就行了。

class Solution {
    int sum  = 0;
    TreeNode* _convertBST(TreeNode* root) {
        if(root == nullptr){
            return root;
        }
        _convertBST(root->right);
        sum += root->val;
        root->val = sum;
        _convertBST(root->left);
        return root;
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        if(root == nullptr){
            return root;
        }
        return _convertBST(root);
    }
};

如果要用迭代法，同样是中序遍历的迭代模板，将左右子树遍历的顺序修改一下就可以了。以下代码来自代码随想录

class Solution {
private:
    int pre; // 记录前一个节点的数值
    void traversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) {
                st.push(cur);
                cur = cur->right;   // 右
            } else {
                cur = st.top();     // 中
                st.pop();
                cur->val += pre;
                pre = cur->val;
                cur = cur->left;    // 左
            }
        }
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        pre = 0;
        traversal(root);
        return root;
    }
};

129 求根节点到叶节点数字之和

https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的所有数字之和。

叶节点是指没有子节点的节点。

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

这道题和前文做过的路径总和类似，只不过路径总和是二叉树到叶子节点的整个路径上节点的和，而这道题让我们把二叉树从根到叶子节点的路径视作一个数字来处理。

所以可以用前序遍历（根左右）的方式，给每个二叉树到叶子节点的路径创建一个数组，将节点值尾插。并在叶子节点将这个数组转成int值，作为其中一个数字插入到retV最终数组中。在主函数内，先调用递归函数，然后再遍历retV数组相加里面的值就可以了。

这道题需要注意的是，我们需要在叶子节点做插入retV的处理，而不是在空节点中做。如果在空节点中做处理，那么一条路径的数字会被插入retV两次（因为叶子节点递归的左子树和右子树都是空，会被操作两次。）

class Solution {
    vector<int> retV;
    // 数组转为int
    int vector2int(vector<int>& v) {
        int sum = 0;
        for (int i = 0; i < v.size(); i++) {
            sum = sum * 10 + v[i];
        }
        return sum;
    }

    void _sumNumbers(TreeNode* root, vector<int> curV) {
        if(root == nullptr){
            return; // 空节点不做任何处理
        }
        // 到叶子节点就需要插入了，不然会额外多处理一次
        if (root->right == nullptr && root->left == nullptr) {
            curV.push_back(root->val);        // 叶子节点的值
            retV.push_back(vector2int(curV)); // 插入返回值数组
            return;
        }
        // 前序遍历
        curV.push_back(root->val);
        _sumNumbers(root->left, curV);
        _sumNumbers(root->right, curV);
    }

public:
    int sumNumbers(TreeNode* root) {
        _sumNumbers(root, vector<int>());
        int sum = 0;
        for (auto& i : retV) {
            sum += i;
        }
        return sum;
    }
};

1382 将二叉搜索树变平衡

https://leetcode.cn/problems/balance-a-binary-search-tree/description/

给你一棵二叉搜索树，请你返回一棵平衡后的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种。

如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是平衡的。

1
2
3

输入：root = [1,null,2,null,3,null,4,null,null]
输出：[2,1,3,null,null,null,4]
解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。

这道题其实是两道题的结合：将搜索二叉树转为有序数组+108从有序数组构造平衡搜索二叉树。我们将给定的搜索二叉树按中序遍历的方式存入数组，即得到了一个有序数组，再根据这个有序数组构造平衡二叉树即可

class Solution {
    // 中序遍历转数组
    void treeToVector(TreeNode* root, vector<int>& v) {
        if (root == nullptr) {
            return;
        }
        treeToVector(root->left,v);
        v.push_back(root->val);
        treeToVector(root->right,v);
    }

    TreeNode* vectorToBanlanceBST(vector<int>& v, int left, int right) {
        // right是开区间，left=right的情况也是无效的
        if (left >= right) {
            return nullptr;
        }
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(v[mid]);
        root->left = vectorToBanlanceBST(v, left, mid);
        root->right = vectorToBanlanceBST(v, mid + 1, right);
        return root;
    }

public:
    TreeNode* balanceBST(TreeNode* root) {
        if(root == nullptr){
            return nullptr;
        }
        vector<int> v;
        // 先用中序遍历转成数组（题目给的已经是一个二叉搜索树，中序遍历肯定有序）
        treeToVector(root, v);
        // 然后用108有序数组转成二叉平衡树的思路来转换
        return vectorToBanlanceBST(v, 0, v.size());
    }
};