Skip to main content

6-二叉数

二叉树的种类

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

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

二叉搜索树：二叉搜索树是一个有序树

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉排序树

平衡二叉搜索树：平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn，注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_set底层实现是哈希表。

二叉树主要有两种遍历方式：

  1. 深度优先遍历：先往深走，遇到叶子节点再往回走。
  2. 广度优先遍历：一层一层的去遍历。

这两种遍历是图论中最基本的两种遍历方式，后面在介绍图论的时候 还会介绍到。

那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：

  • 深度优先遍历
    • 前序遍历（递归法，迭代法）
    • 中序遍历（递归法，迭代法）
    • 后序遍历（递归法，迭代法）
  • 广度优先遍历
    • 层次遍历（迭代法）

这里前中后，其实指的就是中间节点的遍历顺序

  • 前序遍历：中左右
  • 中序遍历：左中右
  • 后序遍历：左右中

二叉树的定义

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

递归三部曲​

  1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
  2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
  3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

1.二叉数遍历​

1.1 递归遍历​

144. 二叉树的前序遍历​

class Solution {
    vector<int> res;
    void preorder(TreeNode* root)
    {
        if (!root) return;
        res.push_back(root->val); //中
        preorder(root->left); //左
        preorder(root->right);//右
    }
public:
    vector<int> preorderTraversal(TreeNode* root) {
        preorder(root);
        return res;
    }
};

94. 二叉树的中序遍历​

class Solution {
public:
    void pri(TreeNode* root,vector<int> &node)
    {
        if (root == NULL) return; //结点为空return null
        else{
            pri(root->left,node);//左
            node.push_back(root->val);//中
            pri(root->right,node);//右
        }
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        pri(root ,res);
        return res;
    }
};



145. 二叉树的后序遍历​

class Solution {
public:
    void pri(TreeNode* root,vector<int> &node)
    {
        if (root == NULL) return; //结点为空return null
        else{
            pri(root->left,node);//左
            pri(root->right,node);//右
            node.push_back(root->val);//中
        }
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        pri(root ,res);
        return res;
    }
};

1.2 非递归遍历​

144. 二叉树的前序遍历​

//前序遍历
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode *> st;
        st.push(root);
        while (!st.empty())
        {
            TreeNode *temp  = st.top();
            st.pop();
            if (temp!=NULL) res.push_back(temp->val); //中
            else continue;
            st.push(temp->right); //后 右
            st.push(temp->left); //先 左
        }
        return res;
    }
};

94. 二叉树的中序遍历​

class Solution {
public:

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        while (!st.empty() || root)
        {
            if (root)
            {
                st.push(root);
                root = root->left;
            }
            else
            {
                root = st.top();
                st.pop();
                res.push_back(root->val);
                root = root->right;
            }
        }
        return res;
    }
};

145. 二叉树的后序遍历​

//后序遍历
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode *> st;
        st.push(root);
        while (!st.empty())
        {
            TreeNode *temp  = st.top();
            st.pop();
            if (temp!=NULL) res.push_back(temp->val); //中
            else continue;
            st.push(temp->left);//后 左
            st.push(temp->right);//先 右
        }
        reverse(res.begin(), res.end()); //反过来左中右
        return res;
    }
};

589. N 叉树的前序遍历​

//589. N 叉树的前序遍历
class Solution {
public:
    void pre(Node* root,vector<int> &res)
    {
        if (root==NULL) return;
        else
        {
            res.push_back(root->val);
            for (int i = 0; i < (root->children).size(); ++i) {
                pre((root->children)[i],res);
            }
        }
    }
    vector<int> preorder(Node* root) {
        vector<int> res;
        pre(root,res);
        return res;
    }
};

590. N 叉树的后序遍历​

//590. N 叉树的后序遍历
class Solution {
public:
    void pre(Node* root,vector<int> &res)
    {
        if (root==NULL) return;
        else
        {

            for (int i = 0; i < (root->children).size(); ++i) {
                pre((root->children)[i],res);
            }
            res.push_back(root->val);
        }
    }
    vector<int> postorder(Node* root) {
        vector<int> res;
        pre(root,res);
        return res;
    }
};

1.3 层序遍历​

102. 二叉树的层序遍历​

//102. 二叉树的层序遍历
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> res;
        if (root!=NULL) que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            vector<int> tmp;
            while (size--)
            {
                TreeNode* tp = que.front();
                que.pop();
                tmp.push_back(tp->val);
                if(tp->left!=NULL) que.push(tp->left);
                if(tp->right!=NULL) que.push(tp->right);
            }
            res.push_back(tmp);
        }

        return res;
    }
};

107. 二叉树的层序遍历 II​

//107. 二叉树的层序遍历 II
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> res;
        if (root!=NULL) que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            vector<int> tmp;
            while (size--)
            {
                TreeNode* tp = que.front();
                que.pop();
                tmp.push_back(tp->val);
                if(tp->left!=NULL) que.push(tp->left);
                if(tp->right!=NULL) que.push(tp->right);
            }
            res.push_back(tmp);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

199. 二叉树的右视图​

//199. 二叉树的右视图
class Solution {
    //层序遍历最后一个节点加进去
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> res;
        if (root!=NULL) que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            while (size--)
            {
                TreeNode* tp = que.front();
                que.pop();
                if(size==0) res.push_back(tp->val);
                if(tp->left!=NULL) que.push(tp->left);
                if(tp->right!=NULL) que.push(tp->right);
            }
        }
       
        return res;
    }
};

637. 二叉树的层平均值​

//637. 二叉树的层平均值
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> que;
        vector<double> res;
        if (root!=NULL) que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            int f = size;
            vector<int> tmp;
            double s = 0;
            while (size--)
            {
                TreeNode* tp = que.front();
                que.pop();
                s+=tp->val;

                if(tp->left!=NULL) que.push(tp->left);
                if(tp->right!=NULL) que.push(tp->right);
            }
            res.push_back(s / f);
        }

        return res;
    }
};

429. N 叉树的层序遍历​

//429. N 叉树的层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*> que;
        vector<vector<int>> res;
        if (root!=NULL) que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            vector<int> tmp;
            while (size--)
            {
                Node* tp = que.front();
                que.pop();
                tmp.push_back(tp->val);

                for (int i = 0; i < (tp->children).size(); ++i) {
                    que.push((tp->children)[i]);
                }

            }
            res.push_back(tmp);
        }

        return res;
    }
};

515. 在每个树行中找最大值​

//515. 在每个树行中找最大值
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> res;
        if (root!=NULL) que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            vector<int> tmp;
            int ma = INT_MIN;
            while (size--)
            {
                TreeNode* tp = que.front();
                que.pop();
                if (ma < tp->val) ma = tp->val;

                if(tp->left!=NULL) que.push(tp->left);
                if(tp->right!=NULL) que.push(tp->right);
            }
            res.push_back(ma);
        }

        return res;
    }
};

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

117. 填充每个节点的下一个右侧节点指针 II​

//116. 填充每个节点的下一个右侧节点指针
//117. 填充每个节点的下一个右侧节点指针 II (都可以用)
class Solution {
public:
    Node* connect(Node* root){
        queue<Node*> que;

        if (root!=NULL) que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            vector<int> tmp;
            while (size--)
            {
                Node* tp = que.front();
                que.pop();
                tmp.push_back(tp->val);
                if(tp->left!=NULL) que.push(tp->left);
                if(tp->right!=NULL) que.push(tp->right);
                if(size == 0) tp->next = NULL;
                else
                {
                    tp->next = que.front();
                }
            }
        }
        return root;
    }
};

559. N 叉树的最大深度​

//559. N 叉树的最大深度
class Solution {
public:
    int maxDepth(Node* root) {
        queue<Node*> que;
        if (root == NULL)return 0;
        que.push(root);
        int deep = 1;
        while (!que.empty())
        {
            int size = que.size();
            while (size--)
            {
                Node* tmp = que.front();
                que.pop();
                for (int i = 0; i < (tmp->children).size(); ++i) {
                    que.push((tmp->children)[i]);
                }
            }
            deep++;
        }
        return deep;
    }
};


//递归
class Solution {
public:
    int maxDepth(Node* root) {
        if(!root) return 0;
        int maxdeep = 0;
        for(int i = 0; i < root->children.size();i++)
        {
            maxdeep = max(maxdeep,maxDepth(root->children[i]));
        }
        return maxdeep + 1;
    }
};

104. 二叉树的最大深度​

//递归法
class Solution {
public:
    int maxDepth(TreeNode* root){
        if (root == NULL) return 0;
        int deep = max(maxDepth(root->left),maxDepth(root->right)) + 1;
        return deep;

    }
};

//层序遍历
class Solution {
public:
    int maxDepth(TreeNode* root){

        queue<TreeNode *> que;
        vector<vector<int>> res;
        if (root != NULL) que.push(root);
        int deep = 0;
        while (!que.empty()) {
            deep++;
            int size = que.size();
            vector<int> tmp;
            while (size--) {
                TreeNode *tp = que.front();
                que.pop();
                tmp.push_back(tp->val);
                if (tp->left != NULL) que.push(tp->left);
                if (tp->right != NULL) que.push(tp->right);
            }
            res.push_back(tmp);
        }

        return deep;

    }
};

111. 二叉树的最小深度​

//111.二叉树的最小深度
class Solution {
public:
    int minDepth(TreeNode* root){

        queue<TreeNode *> que;
        if (root != NULL) que.push(root);
        int deep = 0;
        while (!que.empty()) {
            deep++;
            int size = que.size();
            vector<int> tmp;
            while (size--) {
                TreeNode *tp = que.front();
                que.pop();
                tmp.push_back(tp->val);
                if(tp->left == NULL && tp->right== NULL) return deep;
                if (tp->left != NULL) que.push(tp->left);
                if (tp->right != NULL) que.push(tp->right);
            }
        }
        return deep;

    }
};

public:
    int minDepth(TreeNode* root) {
        //回溯
        if(!root) return 0;
        int res = INT_MAX;
        function<void(TreeNode* ,int)> dfs = [&](TreeNode* r,int count)
        {
            if(!r->left && !r->right) 
            {
                res = min(count + 1,res);
                return;
            }
            if(r->left) dfs(r->left,count + 1);
            if(r->right) dfs(r->right,count + 1);
        };
        dfs(root,0);
        return res;
    }
};

其余题目​

226. 翻转二叉树​

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return nullptr;
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->right = left;
        root->left = right;
        return root;
    }
};

101. 对称二叉树​

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        function<bool(TreeNode*  , TreeNode* )> isSymmetric= [&](TreeNode* left , TreeNode* right)
        {
            if(left && !right || !left && right) return false;
            if(!left && !right) return true;
            if(left->val != right->val) return false;
            return isSymmetric(left->left,right->right) && isSymmetric(left->right,right->left);
        };
        if(!root) return true;
        return isSymmetric(root->left , root->right);
    }
};

100. 相同的树​

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p && !q || !p && q) return false;
        if(!p && !q) return true;
        if(p->val != q->val) return false;
        return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
    }
};

572. 另一棵树的子树​

class Solution {
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p && !q || !p && q) return false;
        if(!p && !q) return true;
        if(p->val != q->val) return false;
        return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
    }
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(root && !subRoot || !root && subRoot) return false;
        if(!root && !subRoot) return true;
        if(isSameTree(root, subRoot)) return true;
        else return isSubtree(root->left, subRoot) ||isSubtree(root->right, subRoot);
    }
};

110. 平衡二叉树​

class Solution {

public:
    bool isBalanced(TreeNode* root) {
        function<pair<bool,int>(TreeNode*)> isBalanced = [&](TreeNode* root)
        {
            if(!root) return pair<bool,int>(true,0);
            pair<bool,int> left = isBalanced(root->left);
            pair<bool,int> right = isBalanced(root->right);
            if(!left.first || !right.first) return pair<bool,int>(false,max(left.second , right.second) + 1);
            if(abs(left.second - right.second) > 1) return pair<bool,int>(false,max(left.second , right.second) + 1);
            return pair<bool,int>(true,max(left.second , right.second) + 1);
        };
        return isBalanced(root).first;
    }
};

222. 完全二叉树的节点个数​

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root) return 0;
        int left = 0 , right = 0;
        TreeNode* l = root;
        TreeNode* r = root;
        while(l)
        {
            left++;
            l = l->left;
        }
        while(r)
        {
            right++;
            r = r->right;
        }
        
        if(left == right) return pow(2, right) - 1;
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

257. 二叉树的所有路径​

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        function<void(TreeNode* ,string)> dfs = [&](TreeNode* root,string tmp)
        {
            if(!root) return;
            tmp = tmp + to_string(root->val);
            if(!root->left && !root->right) 
            {
                res.push_back(tmp);
                return;
            }
            dfs(root->left,tmp+"->");
            dfs(root->right,tmp+"->");
        };
        dfs(root,"");
        return res;
    }
};

404. 左叶子之和​

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(!root) return 0;
        int left = sumOfLeftLeaves(root->left);
        int right = sumOfLeftLeaves(root->right);
        if(root->left && !root->left->left && !root->left->right) return root->left->val + left + right;
        else return left + right;
    }
};

513. 找树左下角的值​

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode* > que;
        que.push(root);
        int res = 0;
        while(!que.empty())
        {
            int n = que.size() ,k = 0;
            while(n--)
            {
                TreeNode* top = que.front();
                if(k++ == 0) res = top->val;
                que.pop();
                if(top->left) que.push(top->left);
                if(top->right) que.push(top->right);
            }
        }
        return res;
    }
};

112. 路径总和​

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root) return false;
        if (!root->left && !root->right && root->val == targetSum) return true;
        if (!root->left && !root->right && root->val != targetSum) return false;
        bool left = hasPathSum(root->left, targetSum-root->val);
        bool right = hasPathSum(root->right, targetSum-root->val);
        return left||right;
    }
};

113. 路径总和 II​

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> res;
        vector<int> tmp;
        function<void(TreeNode* , int )> dfs = [&](TreeNode* root, int targetSum)
        {
            if(!root) return;
            tmp.push_back(root->val);
            if(!root->left && !root->right && root->val == targetSum) 
            {
                res.push_back(tmp);
                tmp.pop_back();
                return;
            }
            dfs(root->left,targetSum - root->val);
            dfs(root->right,targetSum - root->val);
            tmp.pop_back();
        };
        dfs(root,targetSum);
        return res;
    }
};

437. 路径总和 III​

class Solution {
public:
    int count = 0;
    int pathSum(TreeNode* root, int sum) {
        if (!root) return 0;
        dfs(root, sum) ;
        pathSum(root->left, sum) ;
        pathSum(root->right, sum);
        return count;
    }
    void dfs(TreeNode* root, long long sum) {
        if (!root) return;
        if (sum - root->val == 0) count++;
        dfs(root->left, sum - root->val);
        dfs(root->right, sum - root->val);
    }
};

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

class Solution {
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder,int preorder_start,int preorder_end,int inorder_start,int inorder_end)
    {
        if(preorder_start == preorder_end) return nullptr;
        TreeNode* root = new TreeNode(preorder[preorder_start]);
        if(preorder_end - preorder_start == 1) return root;
        int pos = inorder_start;
        while(inorder[pos] != preorder[preorder_start]) pos++;
        
        root->left = buildTree(preorder, inorder,preorder_start + 1,preorder_start + 1 + pos - inorder_start,inorder_start,pos);
        root->right = buildTree(preorder, inorder,preorder_start + 1 + pos - inorder_start,preorder_end,pos + 1,inorder_end);
        
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
         return buildTree(preorder, inorder,0,preorder.size(),0,inorder.size());
    }
};

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

class Solution {
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder,int inorder_start,int inorder_end,int postorder_start,int postorder_end)
    {
        if(inorder_end == inorder_start) return nullptr;
        TreeNode* root = new TreeNode(postorder[postorder_end - 1]);
        if(inorder_end - inorder_start == 1) return root;
        int pos = inorder_start;
        while(inorder[pos] != postorder[postorder_end - 1]) pos++;
        
        root->left = buildTree(inorder, postorder,inorder_start,pos,postorder_start,postorder_start + pos - inorder_start);
        root->right = buildTree(inorder, postorder,pos + 1,inorder_end,postorder_start + pos - inorder_start,postorder_end - 1);

        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return buildTree(inorder, postorder,0,inorder.size(),0,postorder.size());
    }
};

654. 最大二叉树​

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if(nums.size() == 0) return nullptr;
        if(nums.size() == 1) return new TreeNode(nums[0]);
        int MAX = nums[0], pos = 0;
        for(int i = 0; i < nums.size();i++) 
        {
            if(nums[i] > MAX)
            {
                MAX = nums[i];
                pos = i;
            }
        }
        TreeNode* root = new TreeNode(MAX);
        vector<int> left(nums.begin(),nums.begin() + pos);
        vector<int> right(nums.begin() + pos + 1,nums.end());
        root->left = constructMaximumBinaryTree(left);
        root->right = constructMaximumBinaryTree(right);
        return root;
    }
};

617. 合并二叉树​

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1 && !root2) return nullptr;
        if(!root1) return root2;
        if(!root2) return root1;
        root1->val += root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        return root1;
    }
};

700. 二叉搜索树中的搜索​

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(!root) return nullptr;
        if(root->val == val) return root;
        else if(root->val > val) return searchBST(root->left, val);
        else return searchBST(root->right, val);
    }
};

98. 验证二叉搜索树​

class Solution {
    TreeNode* pre = nullptr;
public:
    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        bool left = isValidBST(root->left);
        if(pre && root->val <= pre->val) return false;
        pre = root;
        bool right = isValidBST(root->right);
        return left && right;
    }
};

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

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        TreeNode* pre = nullptr;
        int res = INT_MAX;
        function<void(TreeNode*)> search = [&](TreeNode* root){
            if(!root) return;
            search(root->left);
            if(pre) res = min(res,root->val - pre->val);
            pre = root;
            search(root->right);
        };
        search(root);
        return res;
    }
};

501. 二叉搜索树中的众数​

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        int MAX_COUNT = 0;
        unordered_map<int,int> umap;
        function<void(TreeNode* )> search = [&](TreeNode* root)
        {
            if(!root) return;
            search(root->left);
            umap[root->val]++;
            MAX_COUNT =  max(umap[root->val],MAX_COUNT);
            search(root->right);
        };
        search(root);
        for(auto x:umap) 
            if(x.second == MAX_COUNT)
                res.push_back(x.first);
        return res;
    }
};

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

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return nullptr;
        if(root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left,  p,  q);
        TreeNode* right = lowestCommonAncestor(root->right,  p,  q);
        if(left && right) return root;
        if(right) return right;
        else return left;
    }
};

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

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return NULL;  //此节点为空直接return
        TreeNode* find = NULL;
        if (root->val > p->val && root->val > q->val)
        {
            find = lowestCommonAncestor(root->left,p,q);
        }
        if (root->val < p->val && root->val < q->val)
        {
            find = lowestCommonAncestor(root->right,p,q);
        }
        if (find) return find;
        return root;
    }
};

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

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root) return new TreeNode(val);
        if (root-> val > val ) root->left = insertIntoBST(root->left, val);
        if (root-> val < val ) root->right = insertIntoBST(root->right, val);
        return root;
    }
};

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

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(!root) return nullptr;
        if(root->val == key)
        {
            if(!root->left) return root->right;
            if(!root->right) return root->left;
            //两个都不为空
            TreeNode* l = root->left;
            TreeNode* r = root->right;
            TreeNode* cur = r;
            while(cur->left) cur = cur->left;
            cur->left = l;
            return r;

        }
        else
        {
            root->left = deleteNode(root->left,key);
            root->right = deleteNode(root->right,key);
        }
        return root;
    }
};

669. 修剪二叉搜索树​

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(!root) return nullptr;
        if(root->val < low) return trimBST(root->right,  low,  high);
        if(root->val > high) return trimBST(root->left,  low,  high);
        root->left=trimBST(root->left,  low,  high);
        root->right=trimBST(root->right,  low,  high);
        return root;
    }
};

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

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

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

class Solution {
    TreeNode* pre = nullptr;
public:
    TreeNode* convertBST(TreeNode* root) {
        if(!root) return root;
        TreeNode* right = convertBST(root->right);
        if(pre) root->val += pre->val;
        pre = root;
        TreeNode* left = convertBST(root->left);
        return root;
    }
};

1382. 将二叉搜索树变平衡​

class Solution {
    vector<TreeNode*> res;
    //中序遍历二叉数
    void search(TreeNode* root)
    {
        if(!root) return;
        search(root->left);
        res.push_back(root);
        search(root->right);
    }
    //平衡二叉数构建
    TreeNode* sortedArrayToBST(int start , int end)
    {
        if(start == end) return nullptr;
        int mid = (start + end) / 2;
        TreeNode* root = res[mid];
        root->left = sortedArrayToBST(start ,  mid);
        root->right = sortedArrayToBST( mid + 1 ,  end);
        return root;
    }
public:
    TreeNode* balanceBST(TreeNode* root) {
        search(root);
        return sortedArrayToBST(0,res.size());
    }
};

543. 二叉树的直径​

class Solution {
    int MAX_COUNT = 0;
    int longest(TreeNode* root) {
        if(!root) return 0;
        int left = longest(root->left);
        int right = longest(root->right);
        MAX_COUNT = max(MAX_COUNT,left + right + 1);
        return max(left,right) + 1;
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        longest(root);
        return MAX_COUNT - 1;
    }
};

1110. 删点成林​

class Solution {
    vector<TreeNode*>res;
    TreeNode* bianli(TreeNode* root,vector<int>& to_delete)
    {
        if (!root) return NULL;
        //删除这一个节点
        if (std::find(to_delete.begin(), to_delete.end(),root->val)!=to_delete.end())
        {
            TreeNode *t = NULL;
            if(root->left)
            {
                t = bianli( root->left,to_delete);
                if (t) res.push_back(t);
            }
            t = NULL;
            if(root->right)
            {
                t = bianli( root->right,to_delete);
                if (t) res.push_back(t);
            }
            return NULL;
        }
        root->left = bianli( root->left,to_delete);
        root->right = bianli( root->right,to_delete);
        return root;
    }
public:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        TreeNode* rs =  bianli(root, to_delete);
        if (rs)res.push_back(rs);
        return res;
    }
};

99. 恢复二叉搜索树​

class Solution {
    vector<int> res;
    int count = 0;
    void trade(TreeNode* root,bool flag)
    {
        if (!root) return;
        trade(root->left,flag);
        if (!flag) res.push_back(root->val);
        else root->val = res[count++];
        trade(root->right,flag);
    }
public:
    void recoverTree(TreeNode* root) {
        trade(root, false);
        std::sort(res.begin(), res.end());
        trade( root,true);
    }
};

653. 两数之和 IV - 输入二叉搜索树​

class Solution {
    unordered_set<int> uset;
public:
    bool findTarget(TreeNode* root, int k) {
        if (!root) return false;
        if (!uset.empty() && uset.find(root->val) != uset.end()) return true;
        uset.insert(k - root->val);
        return findTarget( root->left,  k)||findTarget( root->right,  k);
    }
};

653. 两数之和 IV - 输入二叉搜索树​

class Solution {
    unordered_set<int> uset;
public:
    bool findTarget(TreeNode* root, int k) {
        if (!root) return false;
        if (!uset.empty() && uset.find(root->val) != uset.end()) return true;
        uset.insert(k - root->val);
        return findTarget( root->left,  k)||findTarget( root->right,  k);
    }
};

897. 递增顺序搜索树​

class Solution {
    TreeNode* pre = new TreeNode(0);
    TreeNode* cur = pre;
public:
    TreeNode* increasingBST(TreeNode* root) {
        if(!root) return nullptr;
        increasingBST(root->left);
        pre->right = root;
        pre = root;
        pre->left = nullptr;
        increasingBST(root->right);
        return cur->right;
    }
};

109. 有序链表转换二叉搜索树​

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if(!head) return nullptr;
        if(!head->next) return new TreeNode(head->val);
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* pre = nullptr;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            pre = slow;
            slow = slow->next;
        }
        if(pre)pre->next = nullptr;
        TreeNode* root = new TreeNode(slow->val);
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(slow->next);
        return root;
    }
};

114. 二叉树展开为链表​

class Solution {

public:
    void flatten(TreeNode* root) {
        vector<TreeNode*> res;
        TreeNode* cur = root;
        function<void(TreeNode*)> flat = [&](TreeNode* root)
        {
            if(!root) return ;
            res.push_back(root);
            flat(root->left);
            flat(root->right);
        };
        flat(cur);
        for(int i = 1 ; i < res.size();i++)
        {
            res[i - 1]->left = nullptr;
            res[i - 1]->right = res[i];
        }
    }
};

124. 二叉树中的最大路径和​

class Solution {
    int maxs = INT_MIN;
    int maxPath(TreeNode* root)
    {
        if(!root) return 0;
        int left = maxPath(root->left);
        int right = maxPath(root->right);
        maxs = max({left + right + root->val,maxs,root->val,left+root->val,right+root->val});
        return max({left+root->val,right+root->val,root->val});
    }
public:
    int maxPathSum(TreeNode* root) {
        int res = maxPath( root);
        return max(res,maxs);
    }
};

297. 二叉树的序列化与反序列化​

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root) return "#_";
        string s = to_string(root->val) + "_" +serialize(root->left)  + serialize(root->right);
        //cout << s;
        return s;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        queue<string> que;
        stringstream ss(data);
        string s;
        while(getline(ss,s,'_'))
        {
            que.push(s);
        }
        return construct(que);
    }

        TreeNode *construct(queue<string> &que)
        {
            string val = que.front();
            que.pop();
            if (val == "#") return NULL;
            TreeNode* head = new TreeNode(stoi(val));
            head->left = construct(que);
            head->right = construct(que);
            return head;
        };
};

437. 路径总和 III​

class Solution {
    long long sum = 0;
    void trace(TreeNode* root, long long targetSum)
    {
        if(!root) return;
        if(root->val == targetSum)sum++;
        trace( root->left, targetSum-root->val);
        trace( root->right, targetSum-root->val);
    }
public:
    int pathSum(TreeNode* root, int targetSum) {
        if(!root) return 0;
        trace(root , targetSum);
        pathSum(root->left, targetSum);
        pathSum(root->right, targetSum);
        return sum;
    }
};

剑指 Offer 26. 树的子结构​

class Solution {
    bool SubStructure(TreeNode* A, TreeNode* B)
    {
        //判断两棵树是否相等
        if(!B) return true;
        else if(!A || A->val != B->val) return false;
        return SubStructure(A->left, B->left) && SubStructure(A->right, B->right);

    }
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!B) return false;
        if(!A && !B) return true;
        if(!A) return false;
        bool y = SubStructure(A, B);
        if(y) return true;
        return isSubStructure(A->left,  B) || isSubStructure(A->right, B);
    }
};

剑指 Offer 36. 二叉搜索树与双向链表​

class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(!root) return nullptr;
        Node* head = nullptr;
        Node* pre = nullptr;
        function<void(Node* )> func = [&](Node* root)
        {
            if(!root) return;
            func(root->left);
            if(pre) pre->right = root;
            else head = root;
            root->left = pre;
            pre = root;
            func(root->right);
        };
        func(root);
        head->left = pre;
        pre->right = head;
        return head;
    }
};

剑指 Offer 54. 二叉搜索树的第k大节点​

class Solution {
    int res;
    void bian(TreeNode* root, int &k)
    {
        if(!root) return;
        bian(root->right,  k);
        if(--k == 0) 
        {
            res = root->val;
            return;
        }
        bian(root->left,  k);
    }
public:
    int kthLargest(TreeNode* root, int k) {
        bian(root, k);
        return res;
    }
};

LCR 043. 完全二叉树插入器​

class CBTInserter {
    vector<TreeNode*> res;
    TreeNode* head_root;
public:
    CBTInserter(TreeNode* root) {
        head_root = root;
        //层序遍历
        queue<TreeNode*> que;
        if(root) que.push(root);
        while(!que.empty())
        {
            int n = que.size();
            while(n--)
            {
                TreeNode* top = que.front();
                res.push_back(top);
                que.pop();
                if(top->left)  que.push(top->left);
                if(top->right)  que.push(top->right);
            }
        }
    }
    
    int insert(int v) {
        TreeNode* t = new TreeNode(v);
        if(!head_root) head_root = t;
        res.push_back(t);
        int pos = res.size() / 2 - 1; 
        if(res.size() % 2 == 0) res[pos]->left = t;
        else res[pos]->right = t;
        return res[pos]->val;
    }
    
    TreeNode* get_root() {
        return head_root;
    }
};

LCR 047. 二叉树剪枝​

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if(!root) return root;
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        if(root->val == 0 && !root->left && !root->right) return nullptr;
        return root;
    }
};

LCR 053. 二叉搜索树中的中序后继​

class Solution {
    TreeNode* pre;
    TreeNode* next = nullptr;
    void bian(TreeNode* root, TreeNode* p)
    {
        if(!root) return;
        bian(root->left, p);
        if(pre && pre == p) 
        {
            next = root;
            pre = root;
            return;
        }
        pre = root;
        bian(root->right, p);
    }
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        bian(root, p);
        return next;
    }
};

LCR 055. 二叉搜索树迭代器​

class BSTIterator {
    vector<int> res;
    int cur;
    void bian(TreeNode* root)
    {
        if(!root) return;
        bian(root->left);
        res.push_back(root->val);
        bian(root->right);
    }
public:
    BSTIterator(TreeNode* root) {
        cur = 0;
        bian(root);
    }
    
    int next() {
        return res[cur++];
    }
    
    bool hasNext() {
        return cur < res.size();
    }
};

1448. 统计二叉树中好节点的数目​

class Solution {
    int count = 0;
    void trace(TreeNode* root , int mx)
    {
        if(!root) return;
        if(root->val >= mx) count++;
        trace(root->left , max(mx,root->val));
        trace(root->right , max(mx,root->val));
    }
public:
    int goodNodes(TreeNode* root) {
        trace(root , INT_MIN);
        return count;
    }
};

1372. 二叉树中的最长交错路径​

class Solution {
    int maxs = 0;
    void bianli(TreeNode* root,int l, int r)
    {
        if(!root) return;
        maxs = max({maxs , l , r});
        bianli(root->left,0, l + 1);
        bianli(root->right,r + 1, 0);
    }
public:
    int longestZigZag(TreeNode* root) {
        bianli(root, 0,0);
        return maxs;
    }
};

面试题 04.02. 最小高度树​

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        function<TreeNode*(int , int)> func = [&](int start , int end) -> TreeNode*{
            if(start > end) return nullptr;
            int mid = (start + end) / 2;
            TreeNode* root = new TreeNode(nums[mid]);
            root->left = func(start,mid - 1);
            root->right = func(mid + 1,end);
            return root;
        };
        return func(0,nums.size() - 1);
    }
};

面试题 04.09. 二叉搜索树序列​

class Solution {
public:
    vector<vector<int>> BSTSequences(TreeNode* root) {
        //dfs + 回溯
        if(!root) return {{}};
        vector<vector<int>> res;
        vector<int>temp;
        deque<TreeNode*> que;
        que.push_back(root);
        function<void()> dfs = [&](){
            if(que.empty())
            {
                res.push_back(temp);
                return;
            }

            int n = que.size();
            while(n--)
            {
                TreeNode* front = que.front();
                que.pop_front();
                temp.push_back(front->val);
                if(front->left) que.push_back(front->left);
                if(front->right) que.push_back(front->right);

                dfs();

                if(front->left) que.pop_back();
                if(front->right) que.pop_back();
                temp.pop_back();
                que.push_back(front);
            }
        };
        dfs();
        return res;
    }
};

951. 翻转等价二叉树​

class Solution {
public:
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        if(!root1 && !root2) return true;
        if(!root1 || !root2) return false;
        if(root1->val != root2->val) return false;

        int left1 = flipEquiv(root1->left,root2->left);
        int left2 = flipEquiv(root1->right,root2->left);
        int right1 = flipEquiv(root1->left,root2->right);
        int right2 = flipEquiv(root1->right,root2->right);

        return (left1 && right2) || (left2 && right1);
    }
};

987. 二叉树的垂序遍历*​

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        //先用中序遍历 ，得到基本的数组 左 上 num
        map<int,map<int,vector<int>>> res;
        function<void(TreeNode*,int ,int)> dfs = [&](TreeNode* root ,int h , int v){
            if(!root) return;
            dfs(root->left,h - 1,v + 1);
            res[h][v].push_back(root->val);
            dfs(root->right,h + 1,v + 1);
        };
        dfs(root,0,0);
        vector<vector<int>> result;
        for(auto x:res)
        {
            vector<int> p;
            for(auto k : x.second)
            {
               vector<int> m = k.second;
               sort(m.begin(),m.end());
               for(auto i : m) p.push_back(i);
            }
            result.push_back(p);
        }
        return result;
    }
};

863. 二叉树中所有距离为 K 的结点**​

class Solution {
public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        
        //存储父子节点
        unordered_map<TreeNode* ,vector<TreeNode*>> umap;
        function<void(TreeNode*)> search = [&](TreeNode* root){
            if(!root) return;
            if(root->left)
            {
                umap[root->left].push_back(root);
                umap[root].push_back(root->left);
                search(root->left);
            }
            if(root->right)
            {
                umap[root->right].push_back(root);
                umap[root].push_back(root->right);
                search(root->right);
            }
        };
        search(root);

        //BFS
        queue<TreeNode*> que;
        unordered_set<TreeNode*> visited;
        vector<int> res;
        que.push(target);
        int count = 0;
        while(!que.empty())
        {
            int n = que.size();
            while(n--)
            {
                TreeNode* top = que.front();
                que.pop();
                visited.insert(top);
                if(count == k)
                {
                    res.push_back(top->val);
                }
                else
                {
                    for(auto x : umap[top])
                        if(visited.find(x) == visited.end()) que.push(x);
                }
            }
            count++;
        }
        return res;
    }
};

662. 二叉树最大宽度​

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        unordered_map<int,pair<long long,long long>> umap;
        function<void(TreeNode*,int,int ,bool)> search = [&](TreeNode* root,int r1,long long r2 , bool init){
            if(!root) return;
            if(init)
            {
                umap[r1].first = INT_MAX;
                umap[r1].second = INT_MIN;
            }
            else
            {
                umap[r1].first = min(umap[r1].first,r2);
                umap[r1].second = max(umap[r1].second,r2);
            }
            search(root->left , r1 + 1, r2 * 2,init);
            search(root->right , r1 + 1, r2 * 2 + 1,init);
        };

        // pair<int,int> 节点号 （deep，1，节点号）
        search(root,0,1,true);
        search(root,0,1,false);
        long long maxs = 0;
        for(auto x : umap)
        {
            pair<int,int> t = x.second;
            cout << t.second << " " << t.first <<endl;
            maxs = max(maxs,(long long)t.second - t.first + 1);
        }
        return maxs;
    }
};

958. 二叉树的完全性检验​

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        vector<int> num;
        function<void(TreeNode* ,int)> search = [&](TreeNode* root, int k)
        {
            if(!root || k > 100) return;
            num.push_back(k);
            search(root->left,k * 2);
            search(root->right,k * 2 + 1);
        };
        search(root,1);
        sort(num.begin(),num.end());
        return num.size() == num.back();
    }
};

662. 二叉树最大宽度​

class Solution {
public:
    int ans=0;
    unordered_map<int,int> mp;
    void dfs(TreeNode* root,int u,int depth) {
        if(root==nullptr) return;
        if(!mp.count(depth)) mp[depth]=u;
        ans=max(ans,u-mp[depth]+1);
        u=u-mp[depth]+1; 
        dfs(root->left,u<<1,depth+1);
        dfs(root->right,u<<1|1,depth+1);
    }
    int widthOfBinaryTree(TreeNode* root) {
        dfs(root,1,0);
        return ans;
    }
};

1325. 删除给定值的叶子节点​

class Solution {
public:
    TreeNode* removeLeafNodes(TreeNode* root, int target) {
        //如果一棵树下面全是相同的target，则删除 return null
        if(!root || root->val == target && !root->left && !root->right) return nullptr;
        root->left = removeLeafNodes(root->left,target);
        root->right = removeLeafNodes(root->right,target);
        if(root->val == target && !root->left && !root->right) return nullptr;
        return root;
    }
};

687. 最长同值路径​

class Solution {
    int Max_len = 0;//保存中间最长节点
    array<int,2> find_max(TreeNode* root)//返回以a[1] 节点的最长长度a[0]
    {
        if(!root) return {0,-5000};
        array<int,2> left = find_max(root->left);
        array<int,2> right = find_max(root->right);
        int cur = 1;
        if(root->val == left[1]) cur += left[0];
        if(root->val == right[1]) cur += right[0];
        Max_len = max(cur,Max_len);
        array<int,2> r = {1,root->val};
        if(root->val == left[1]) r[0] = max(left[0] + 1,r[0]);
        if(root->val == right[1]) r[0] = max(right[0] + 1,r[0]);
        return r;
    }
public:
    int longestUnivaluePath(TreeNode* root) {
        array<int,2> res = find_max(root);
        return max({Max_len - 1,res[0] - 1,0}) ;
    }
};