Skip to main content

二叉数

二叉树的种类

满二叉树：如果一棵二叉树只有度为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;
    }
};

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;

    }
};

//递归
class Solution {
    int minDepth(TreeNode* root,int deep)
    {
        if (!root)return 0;
        if ((!root->left) && (!root->right)) return deep;
        if (!root->left) return minDepth( root->right, deep)+1;
        if (!root->right) return minDepth( root->left, deep)+1;
        return min(minDepth( root->left, deep),minDepth( root->right, deep))+1;
    }
public:
    int minDepth(TreeNode* root){
        return minDepth(root,1);
    }
};

2.其余题目（递归）​

226. 翻转二叉树​

题目难度： 简单 用时： 5分钟 标记： 完成

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


101. 对称二叉树​

题目难度： 简单 用时： 11分钟 标记： 未完成

思路：里层与外层相等

//101. 对称二叉树
class Solution {
    /*
    判断是否可以翻转，递归实现
    
    */
public:
    bool leri(TreeNode* left ,TreeNode* right)
    {
        if (left==NULL && right!=NULL) return false;
        if (right==NULL && left!=NULL) return false;
        if (right==NULL && left==NULL) return true;
        if (right->val != left->val) return false;
        bool out =  leri(left->left ,right->right); //外侧是否相等
        bool insi =  leri(left->right ,right->left); //内测是否相等
        return (out && insi);

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

100. 相同的树​

题目难度： 简单 用时： 5分钟 标记： 完成

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

572. 另一棵树的子树​

题目难度： 简单 用时： 12分钟 标记： 完成

class Solution {
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true;
        if (p && !q) return false;
        if (!p && q) return false;
        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) || !subRoot) return true;
        if (!root && subRoot) return false;
        bool yes,left,right;
        yes = isSameTree(root,subRoot);
        left = isSubtree(root->left,subRoot);
        right = isSubtree(root->right,subRoot);
        return yes||left||right;
    }
};

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

题目难度： 中等 用时： 12分钟 标记： 完成

//222. 完全二叉树的节点个数
//方法一:普通方法
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root == NULL) return 0;
        return countNodes(root->left) + countNodes(root->right) + 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，所以leftDepth初始为0
        }
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

110. 平衡二叉树​

题目难度： 简单 用时： 18分钟 标记： 未完成

//110.平衡二叉树
class Solution {
    int deep(TreeNode* root)
    {
        if (!root) return 0;
        return max(deep( root->left) ,deep(root->right)) + 1;
    }
public:
    bool isBalanced(TreeNode* root) {
        if (!root) return true;
        int l = deep(root->left);
        int r = deep(root->right);
        if (abs(l -r) > 1) return false;
        return isBalanced(root->left) && isBalanced(root->right);
    }
};

257. 二叉树的所有路径​

题目难度： 简单 用时： 9 分钟 标记： 完成

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

404. 左叶子之和​

题目难度： 简单 用时： 4 分钟 标记： 完成

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

513. 找树左下角的值​

题目难度： 简单 用时： 9 分钟 标记： 完成

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode* > que;
        que.push(root);
        int left_fist;
        while (!que.empty())
        {
            int n = que.size();
            left_fist = que.front()->val;//每一层的第一个
            while (n--)
            {
                TreeNode* top = que.front();
                que.pop();
                if (top->left) que.push(top->left);
                if (top->right) que.push(top->right);
            }
        }
        return left_fist;
    }
};

112. 路径总和​

题目难度： 简单 用时： 10 分钟 标记： 完成

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

113. 路径总和 II​

题目难度： 中等 用时： 5 分钟 标记： 完成

class Solution {
    vector<vector<int>> res;
    void traval(TreeNode* root, int targetSum,vector<int> now)
    {
        if (!root) return;
        targetSum-=root->val;
        now.push_back(root->val);
        if (!root->left && !root->right)
        {
            if (targetSum == 0)
                res.push_back(now);
            return;
        }

        traval(root->left,  targetSum,now);
        traval(root->right,  targetSum,now);
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int> now;
        traval(root, targetSum,now);
        return res;
    }
};

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

题目难度： 中等 用时： 20分钟 标记： 完成

//106. 从中序与后序遍历序列构造二叉树
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (postorder.empty()) return NULL;
        // 后序遍历数组最后一个元素，就是当前的中间节点
        int rootValue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootValue);
        // 叶子节点
        if (postorder.size() == 1) return root;
        // 找到中序遍历的切割点
        int delimiterIndex=0;
        while(inorder[delimiterIndex]!=rootValue) delimiterIndex++;
        // 切割中序数组
        // 左闭右开区间：[0, delimiterIndex)
        vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
        // [delimiterIndex + 1, end)
        vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
        // postorder 舍弃末尾元素
        postorder.resize(postorder.size() - 1);
        // 切割后序数组
        // 依然左闭右开，注意这里使用了左中序数组大小作为切割点
        // [0, leftInorder.size)
        vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
        // [leftInorder.size(), end)
        vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());

        root->left = buildTree(leftInorder, leftPostorder);
        root->right = buildTree(rightInorder, rightPostorder);
        return root;
    }
};

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

题目难度： 中等 用时： 20分钟 标记： 完成

//105. 从前序与中序遍历序列构造二叉树
class Solution {
private:
        TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& preorder, int preorderBegin, int preorderEnd) {
        if (preorderBegin == preorderEnd) return NULL;

        int rootValue = preorder[preorderBegin]; // 注意用preorderBegin 不要用0
        TreeNode* root = new TreeNode(rootValue);

        if (preorderEnd - preorderBegin == 1) return root;

        int delimiterIndex;
        for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }
        // 切割中序数组
        // 中序左区间，左闭右开[leftInorderBegin, leftInorderEnd)
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimiterIndex;
        // 中序右区间，左闭右开[rightInorderBegin, rightInorderEnd)
        int rightInorderBegin = delimiterIndex + 1;
        int rightInorderEnd = inorderEnd;

        // 切割前序数组
        // 前序左区间，左闭右开[leftPreorderBegin, leftPreorderEnd)
        int leftPreorderBegin =  preorderBegin + 1;
        int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin; // 终止位置是起始位置加上中序左区间的大小size
        // 前序右区间, 左闭右开[rightPreorderBegin, rightPreorderEnd)
        int rightPreorderBegin = preorderBegin + 1 + (delimiterIndex - inorderBegin);
        int rightPreorderEnd = preorderEnd;

        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  preorder, leftPreorderBegin, leftPreorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, preorder, rightPreorderBegin, rightPreorderEnd);

        return root;
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (inorder.size() == 0 || preorder.size() == 0) return NULL;

        // 参数坚持左闭右开的原则
        return traversal(inorder, 0, inorder.size(), preorder, 0, preorder.size());
    }
};

654. 最大二叉树​

题目难度： 中等 用时： 8分钟 标记： 完成

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if (nums.empty()) return NULL;
        //找到最大值对应的下标
        int max = INT_MIN;
        int index = 0; //最大值下标
        for (int i = 0; i < nums.size(); ++i) {
            if (max < nums[i] )
            {
                max = nums[i];
                index = i;
            }
        }
        //创建节点
        TreeNode* root = new TreeNode(max);
        if (nums.size() == 1) return root;

        vector<int> left(nums.begin(),nums.begin()+index);
        vector<int> right(nums.begin()+index +1,nums.end());
        root->left = constructMaximumBinaryTree(left);
        root->right = constructMaximumBinaryTree(right);
        return root;
    }
};

617. 合并二叉树​

题目难度： 简单 用时： 11分钟 标记： 完成

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (!root1 && !root2) return NULL;
        if (root1 && !root2) return root1;
        if (!root1 && root2)return root2;
        root1->val += root2->val;//合并

        root1->left = mergeTrees(root1->left,  root2->left);
        root1->right = mergeTrees(root1->right,  root2->right);
        return root1;
    }
};

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

题目难度： 简单 用时： 3分钟 标记： 完成

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

98. 验证二叉搜索树​

题目难度： 中等 用时： 9分钟 标记： 完成

//98. 验证二叉搜索树（中序遍历，如果前大于等于后，则false）
class Solution {
    TreeNode* pre = nullptr;
    //中序遍历是有序集合
    bool front_search(TreeNode* root)
    {
        if (!root) return true;
        bool left = front_search(root->left);
        if (pre && pre->val >= root->val) return false;
        pre = root;
        bool right =  front_search(root->right);
        return left && right;
    }
public:
    bool isValidBST(TreeNode* root) {
        return front_search(root);
    }
};

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

题目难度： 简单 用时： 20分钟 标记： 完成

//530. 二叉搜索树的最小绝对差
//方法一：中序遍历法
class Solution {
public:
    void midtraval(TreeNode* root,vector<int> &res)
    {
        if (root==NULL) return;
        midtraval(root->left,res);
        res.push_back(root->val);
        midtraval(root->right,res);
    }
    int getMinimumDifference(TreeNode* root) {

        vector<int> res;
        midtraval(root,res);
        int min_ca = INT32_MAX;

        for (int i = 0; i < res.size()-1; ++i) {
            if ((res[i+1] - res[i]) < min_ca) min_ca = res[i+1] - res[i];
            
        }
        return min_ca;
    }
};

//方法二：双指针法
class Solution {
    int mins = INT_MAX; //定义最小值
    TreeNode* pre = NULL;
public:
    int getMinimumDifference(TreeNode* root) {
        if (!root) return INT_MAX;
        getMinimumDifference(root->left);//遍历左边
        if (pre!=NULL) mins = min(mins,root->val - pre->val);
        pre = root;
        getMinimumDifference(root->right);
        return mins;
    }
};

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

题目难度： 简单 用时： 20分钟 标记： 完成

//501. 二叉搜索树中的众数
class Solution {
public:
    class cmp
    {
    public:
        bool operator()(pair<int,int>a,pair<int,int>b)
        {
            return a.second > b.second;
        }
    };

    void bianli(TreeNode* root,vector<int>& res)
    {
        if (root==NULL)return;
        bianli(root->left,res);
        res.push_back(root->val);
        bianli(root->right,res);
    }
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        bianli(root,res);
        
        map<int,int> ma;
        for (int i = 0; i < res.size(); ++i) {
            ma[res[i]]++;
        }
        vector<pair<int,int>> remap(ma.begin(),ma.end());
        vector<int> ret;
        std::sort(remap.begin(), remap.end(),cmp());
        int fir = 0,maxcount = 0;
        for (auto ma:remap) {
            if (fir==0)
            {
                ret.push_back(ma.first);
                maxcount = ma.second;
            }
            else {
                if (ma.second != maxcount)break;
                ret.push_back(ma.first);
            }
            fir++;
        }
        return ret;

    }
};

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

题目难度： 中等 用时： 10分钟 标记： 完成

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return NULL;  //此节点为空直接return
        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 (left) return left;//左有返回左
        if (right) return right;//右有返回右
        return NULL;
    }
};

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

题目难度： 中等 用时： 分钟 标记： 完成

//235. 二叉搜索树的最近公共祖先
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        if(root == NULL) return NULL;
        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. 二叉搜索树中的插入操作​

题目难度： 中等 用时： 10分钟 标记： 完成

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. 删除二叉搜索树中的节点​

题目难度： 中等 用时： 20 分钟 标记： 未完成

//450. 删除二叉搜索树中的节点
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root == NULL) return NULL;
        if (root->val == key)
        {
            if (root->left==NULL && root->right == NULL) return NULL;
            if (root->left!=NULL && root->right == NULL) return root->left;
            if (root->left==NULL && root->right != NULL)return root->right;
            if (root->left!=NULL && root->right != NULL)
            {
                /*
                这里是找到右子树的中序遍历第一个节点，将left赋值给它，返回root->right
                */
                TreeNode* tmp = root->right;
                while (tmp->left) tmp=tmp->left;
                tmp->left = root->left;
                return root->right;
            }

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

669. 修剪二叉搜索树​

题目难度： 中等 用时： 12 分钟 标记： 未完成

//669. 修剪二叉搜索树（需要递归）
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == NULL) return NULL;
        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. 将有序数组转换为二叉搜索树​

题目难度： 简单 用时： 10分钟 标记： 完成

//108. 将有序数组转换为二叉搜索树
class Solution {
public:
    TreeNode* traval(vector<int>& nums,int left, int right)
    {
        if (left > right) return NULL;
        int mid = (left + right) / 2;
        TreeNode*root = new TreeNode(nums[mid]);
        root->left=traval(nums,left,mid-1);
        root->right=traval(nums,mid+1,right);
        return root;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return traval(nums,0,nums.size()-1);
    }
};

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

题目难度： 中等 用时： 10 分钟 标记： 未完成

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

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

题目难度： 简单 用时： 10分钟 标记： 完成

class Solution {
    int res = 0;
    void backtracking(TreeNode* root,string s)
    {
        if (!root) return;
        string p(1,root->val+'0');
        s +=p;
        if(!root->left && !root->right)
        {
            cout << s << endl;
            res+= stoi(s);
            return;
        }

        backtracking(root->left,s);
        backtracking(root->right,s);
    }
public:
    int sumNumbers(TreeNode* root) {
        backtracking(root,"");
        return res;
    }
};

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

题目难度： 简单 用时： 10分钟 标记： 完成

// 1.有序树转成有序数组
// 2.有序数组转平衡二叉树
class Solution {
    vector<int>res;
    void midtraval(TreeNode* root)
    {
        if (root==NULL) return;
        midtraval(root->left);
        res.push_back(root->val);
        midtraval(root->right);

    }
    TreeNode*  buildtree(int left ,int right)
    {
        if (left>right)  return NULL;
        else if(right == left)
        {
            TreeNode* r = new TreeNode(res[right]);
            return r;
        }
        //数组切分
        TreeNode* tree = new TreeNode(res[(left+right)/2]);
        tree->left = buildtree(left,(left+right)/2-1);
        tree->right =buildtree((left+right)/2+1,right);
        return tree;
    }
public:
    TreeNode* balanceBST(TreeNode* root) {
        //利用中序遍历变成有序数组，然后再构建平衡二叉数
        midtraval(root);
        TreeNode* tree = buildtree(0,res.size()-1);
        return tree;
    }
};

543. 二叉树的直径​

题目难度： 简单 用时： 10分钟 标记： 完成

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

437. 路径总和 III​

首先先序递归遍历每个节点，再以每个节点作为起始点递归寻找满足条件的路径。双递归法

题目难度： 简单 用时： 10分钟 标记： 完成

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, int sum) {
        if (!root) return;
        if (sum - root->val == 0) count++;
        dfs(root->left, sum - root->val);
        dfs(root->right, sum - root->val);
    }
};

1110. 删点成林​

题目难度： 中等 用时： 10分钟 标记： 完成

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. 恢复二叉搜索树​

题目难度： 简单 用时： 10分钟 标记： 完成

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 - 输入二叉搜索树​

题目难度： 简单 用时： 10分钟 标记： 完成

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. 递增顺序搜索树​

题目难度： 简单 用时： 10分钟 标记： 完成

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

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

题目难度： 中等 用时： 10分钟 标记： 完成

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)
        {
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }

        pre->next = nullptr;
        TreeNode* root = new TreeNode(slow->val);
        root->left = sortedListToBST( head);
        root->right = sortedListToBST( slow->next);
        return root;
    }
};

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;
    }
};