树专题刷题笔记

2022.03.12

发布于未知归属地

树二叉树 C++学习分享

二叉树

前言

本文记录我刷二叉树专题的笔记

分析

二叉树原理这里不多说，主要讲解二叉树的一些题型，和做题上的小技巧和模板。

我刷了 100 多道二叉树的题，并且参考其它大佬的博客，把二叉树的题划分为几类：

基础遍历
序列化和反序列化（包括构造二叉树）
求二叉树的属性
二叉树的修改
二叉树路径
BST

其中，遍历是二叉树专题的基础，不像链表，主要以修改为核心，在树的题型中，多数还是以遍历为基础。

基础的 dfs 和 bfs，前中后序层序，都要滚瓜烂熟。

基础的 dfs 掌握递归，栈即可，栈的做法比较难，可以掌握双色标记，至于 morris 的方法，我觉得比较麻烦，就没有掌握。

在做题的过程中，dfs 的递归实现和层序非常高频。

比如 BST 的题型中，中序使用得非常多，而涉及到每层节点的题，则层序使用得比较多，当然也可以 dfs 同时带上层数。构造二叉树的题型，则多是后序，因为从第往上遍历构造会非常方便。

而序列化和反序列化的题，则掌握前中后遍历后左、右、根的顺序即可。

还有一些题型， dfs 的逆序也比较常见，比如 BST 中序是递增的，而中序逆序自然就是递减的，求第 k 大的问题就需要这么做。逆序在使用到栈的时候，也需要这么做，比如双色标记遍历法中，就是普通 dfs 的完全逆序。

至于做题的技巧，我认为不多，可以把根节点都修改为 root，这样比较方便。并且一些模板题，比如层序这种，可以不要复制，自己敲，很快就会非常熟练。

其它还有平衡树，字典树，堆这些树型结构的，则题型和本专题不太一样，所以不涉及。

题型

遍历

二叉树的遍历是最基础的题型，也是许多二叉树题的基础。分为 dfs 和 bfs，dfs 有递归、栈、二色标记、Morris 几种实现， bfs 一般用队列，也可以递归巧妙的实现。

list

144. 二叉树的前序遍历

题意

前序打印二叉树

递归

/**
 * 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 {
    vector<int> res;

public:
    vector<int> preorderTraversal(TreeNode* root) {
        if (!root){
            return res;            
        }
        res.push_back(root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
        return res;
    }
};

时间复杂度： $O (n)$ ，空间复杂度： $O (1)$

栈

根入栈
栈顶元素出栈，然后右、左子节点入栈（为什么要先右？因为实际上是先左后右遍历，但是栈 FILO 的特性，所以要反过来）

/**
 * 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<int> preorderTraversal(TreeNode* root) {
        if (!root){
            return {};
        }

        stack<TreeNode*> s;
        vector<int> res;

        s.push(root);

        while(!s.empty()){
            auto t=s.top();
            s.pop();
            res.push_back(t->val);
            if (t->right){
                s.push(t->right);
            }
            if (t->left){
                s.push(t->left);
            }
        }

        return res;
    }
};

时间复杂度： $O (n)$ ，空间复杂度： $O (n)$

二色表示

/**
 * 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<int> preorderTraversal(TreeNode* root) {
        // val,color
        stack<pair<TreeNode*,int>> s;
        vector<int> res;

        s.push({root,0});

        while(!s.empty()){
            auto t=s.top();
            s.pop();

            if (!t.first){
                continue;
            }

            if (t.second==1){
                res.push_back(t.first->val);                
                continue;
            }

            s.push({t.first->right,0});
            s.push({t.first->left,0});
            s.push({t.first,1});            
        }

        return res; 
    }
};

时间复杂度： $O (n)$ ，空间复杂度： $O (n)$

94. 二叉树的中序遍历

题意

前序打印二叉树

递归

/**
 * 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 {
    vector<int> res;
    
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if (!root){
            return res;
        }

        inorderTraversal(root->left);
        res.push_back(root->val);
        inorderTraversal(root->right);

        return res;
    }
};

时间复杂度： $O (n)$ ，空间复杂度： $O (1)$

栈

/**
 * 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<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> res;

        while(root||!s.empty()){
            while(root){
                s.push(root);
                root=root->left;
            }

            auto t=s.top();
            s.pop();
            res.push_back(t->val);
            root=t->right;
        }

        return res; 
    }
};

时间复杂度： $O (n)$ ，空间复杂度： $O (n)$

二色表示

/**
 * 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<int> inorderTraversal(TreeNode* root) {
 // val,color
        stack<pair<TreeNode*,int>> s;
        vector<int> res;

        s.push({root,0});

        while(!s.empty()){
            auto t=s.top();
            s.pop();

            if (!t.first){
                continue;
            }

            if (t.second==1){
                res.push_back(t.first->val);                
                continue;
            }

            s.push({t.first->right,0});
            s.push({t.first,1});            
            s.push({t.first->left,0});
        }

        return res; 
    }
};

时间复杂度： $O (n)$ ，空间复杂度： $O (n)$

145. 二叉树的后序遍历

题意

前序打印二叉树

递归

/**
 * 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 {
    vector<int> res;

public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (!root){
            return res;
        }
        
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        res.push_back(root->val);
        
        return res;
    }
};

时间复杂度： $O (n)$ ，空间复杂度： $O (1)$

栈

/**
 * 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<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> res;

        while(root||!s.empty()){
            while(root){
                s.push(root);
                if (root->left){
                    root=root->left;
                } else {
                    root=root->right;
                }
            }
            
            auto t=s.top();
            s.pop();
            res.push_back(t->val);

            if (!s.empty()&&t==s.top()->left){
                root=s.top()->right;
            } else {
                root=nullptr;
            }
        }

        return res; 
    }
};

时间复杂度： $O (n)$ ，空间复杂度： $O (n)$

二色表示

/**
 * 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<int> postorderTraversal(TreeNode* root) {
 // val,color
        stack<pair<TreeNode*,int>> s;
        vector<int> res;

        s.push({root,0});

        while(!s.empty()){
            auto t=s.top();
            s.pop();

            if (!t.first){
                continue;
            }

            if (t.second==1){
                res.push_back(t.first->val);                
                continue;
            }

            s.push({t.first,1});            
            s.push({t.first->right,0});
            s.push({t.first->left,0});
        }

        return res; 
    }
};

时间复杂度： $O (n)$ ，空间复杂度： $O (n)$

102. 二叉树的层序遍历

题意

层序遍历二叉树

分析

由于每层进行遍历，显然是 bfs，故使用队列实现

每次循环时，一层的元素都在队列中，所以队列的长度就是这一层的元素个数，这一层全取出来，然后再逐个 push 左右子节点即可。

队列 bfs

/**
 * 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) {
        queue<TreeNode*> q;        
        vector<vector<int>> res;
        
        q.push(root);

        while(root && !q.empty()){
            vector<int> t;

            int size=q.size();

            while(size--){
                root=q.front();
                q.pop();
                t.push_back(root->val);

                if (root->left) {
                    q.push(root->left);
                }           
                if (root->right){
                    q.push(root->right);
                }
            }

            res.push_back(t);
        }

        return res;
    }
};

时间复杂度： $O (n)$ ，空间复杂度： $O (n)$

递归 dfs

这题虽然要层序遍历的结果，但是实际上只要结果是这样即可，过程我们也可以 dfs 来实现，dfs 时，都是 left，right 的顺序，所以在宏观上每一层的顺序仍然没有改变。换句话说，遍历到每一个节点时，只要直到它是哪一层的，然后放到哪一层去即可。

故我们可以在 dfs 过程中，把这个节点的层数也传上去，然后遍历的时候 push 到这一层中去即可。

/**
 * 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 {
    vector<vector<int>> res;

public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        dfs(root,0);
        return res;
    }

    void dfs(TreeNode *root,int level){
        if (!root){
            return;
        }
        if (res.size()<level+1){
            res.push_back({});
        }
        res[level].push_back(root->val);        
        dfs(root->left,level+1);
        dfs(root->right,level+1);
    }
};

时间复杂度： $O (n)$ ，空间复杂度： $O (n)$

107. 二叉树的层序遍历 II

题意

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

分析

reverse(102) 即可

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

/**
 * 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) {
        queue<TreeNode*> q;        
        vector<vector<int>> res;
        
        q.push(root);

        while(root && !q.empty()){
            vector<int> t;

            int size=q.size();

            while(size--){
                root=q.front();
                q.pop();
                t.push_back(root->val);

                if (root->left) {
                    q.push(root->left);
                }           
                if (root->right){
                    q.push(root->right);
                }
            }

            res.push_back(t);
        }

        return {res.rbegin(),res.rend()};
    }
};

103. 二叉树的锯齿形层序遍历

题意

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

分析

按普通的层序遍历来，然后根据层数的奇偶性，如果是奇数，则反转该层即可

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        queue<TreeNode*> q;        
        vector<vector<int>> res;
        bool lr=true;
        
        q.push(root);

        while(root && !q.empty()){
            vector<int> t;

            int size=q.size();

            while(size--){
                root=q.front();
                q.pop();
                t.push_back(root->val);

                if (root->left) {
                    q.push(root->left);
                }           
                if (root->right){
                    q.push(root->right);
                }
            }

            if (!lr){
                reverse(t.begin(),t.end());
            }
            lr=!lr;

            res.push_back(t);            
        }

        return res;
    }
};

987. 二叉树的垂序遍历

题意

给你二叉树的根结点 root ，请你设计算法计算二叉树的 **垂序遍历 序列。

分析

前序遍历获取所有节点的坐标
按列、行、大小的顺序排序

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

/**
 * 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 {
    vector<vector<int>> res;
    map<int,vector<pair<int,int>>> m;

public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        pre(root,0,0);
        for (auto i:m){
            sort(i.second.begin(),i.second.end());

            vector<int> t;
            for (auto j=i.second.begin();j!=i.second.end();j++){
                t.push_back((*j).second);
            }

            res.push_back(t);
        }
        return res;
    }

    void pre(TreeNode *root,int r,int c){
        if (!root){
            return;
        }
        m[c].push_back({r,root->val});
        pre(root->left,r+1,c-1);
        pre(root->right,r+1,c+1);
    }
};

589. N 叉树的前序遍历

题意

给定一个 n 叉树的根节点 root ，返回其节点值的 前序遍历 。

分析

和二叉树前序遍历类似，先读取值，再以此递归子节点

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
    vector<int> res;

public:
    vector<int> preorder(Node* root) {
        pre(root);
        return res;
    }

    void pre(Node *root){
        if (!root){
            return;
        }
        res.push_back(root->val);
        for (auto i:root->children){
            pre(i);
        }
    }
};

590. N 叉树的后序遍历

题意

给定一个 n 叉树的根节点 root ，返回其节点值的 后序遍历 。

分析

和二叉树后序遍历类似，先以此递归子节点，再读取值

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
    vector<int> res;

public:
    vector<int> postorder(Node* root) {
        post(root);
        return res;
    }

    void post(Node *root){
        if (!root){
            return;
        }
        for (auto i:root->children){
            post(i);
        }
        res.push_back(root->val);
    }
};

429. N 叉树的层序遍历

题意

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

分析

和普通的二叉树层序遍历区别不大，只是二叉树是 push 左右子节点，而 n 叉则把所有节点都 push 进队列。

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> res;
        vector<int> n;
        queue<Node*> q;
        q.push(root);

        while(root&&!q.empty()){
            int size=q.size();
            n.clear();

            while(size--){
                auto t=q.front();
                q.pop();
                n.push_back(t->val);

                for (auto i:t->children){
                    if (i){
                        q.push(i);
                    }
                }
            }

            res.push_back(n);
        }

        return res;
    }
};

面试题 04.03. 特定深度节点链表

题意

给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。

分析

题目的意思就是每一层建立一个链表，直接层序遍历即可

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
public:
    vector<ListNode*> listOfDepth(TreeNode* root) {
        vector<ListNode*> res;
        queue<TreeNode*> q;
        q.push(root);

        while(root && !q.empty()){
            int size=q.size();
            ListNode *dummy = new ListNode();            
            ListNode *cur=dummy;

            while(size--){
                auto t=q.front();
                q.pop();

                cur->next=new ListNode(t->val);
                cur=cur->next;
                if (t->left){
                    q.push(t->left);
                }
                if (t->right){
                    q.push(t->right);
                }
            }

            res.push_back(dummy->next);
        }

        return res;
    }
};

构造二叉树

构建二叉树的题是指已经知道了遍历的结果，然后重建原本的二叉树。

list

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

题意

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

分析

前序遍历的结果是：根左右

中序遍历的结果是：左根右

所以对于当前节点，前序遍历第一个元素来构建即可。对于左孩子，找到前中序遍历结果的两个左子数组，同理右孩子即可。

优化

也可以不用构建临时数组，传索引原地也行

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

临时数组

/**
 * 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:
    TreeNode* buildTree(vector<int>& pre, vector<int>& in) {
        if (pre.empty()){
            return nullptr;
        }

        TreeNode *root=new TreeNode(pre[0]);

        vector<int> leftPre,leftIn,rightPre,rightIn;
        bool f=true;

        for (auto &i:in){
            if (i==pre[0]){
                f=false;
                continue;
            }
            if (f){
                leftIn.push_back(i);
                continue;
            }
            rightIn.push_back(i);
        }

        for (int i=1;i<pre.size();i++){
            if (i-1<leftIn.size()){
                leftPre.push_back(pre[i]);
                continue;
            }
            rightPre.push_back(pre[i]);
        }

        root->left=buildTree(leftPre,leftIn);
        root->right=buildTree(rightPre,rightIn);

        return root;
    }
};

原地

/**
 * 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:
    TreeNode* buildTree(vector<int>& pre, vector<int>& in) {        
        return buildNode(pre,0,pre.size()-1,in,0,in.size()-1);
    }

    TreeNode* buildNode(vector<int>& pre,int pbegin,int pend, vector<int>& in,int ibegin,int iend) {
        if (pbegin>pend||ibegin>iend||pend<0||iend<0){
            return nullptr;
        }

        TreeNode *root=new TreeNode(pre[pbegin]);
        int index;

        for (int i=ibegin;i<iend;i++){
            if (in[i]==pre[pbegin]){
                index=i;
                break;
            }
        }

        root->left=buildNode(pre,pbegin+1,pbegin+index-ibegin,in,ibegin,index-1);
        root->right=buildNode(pre,pbegin+index-ibegin+1,pend,in,index+1,iend);

        return root;
    }
};

889. 根据前序和后序遍历构造二叉树

题意

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有无重复值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

分析

前序遍历的结果是：根左右

后序遍历的结果是：左右根

所以，对于当前节点来说，根据前序遍历的第一个元素建立。然后分别建立左右孩子节点，问题在于怎么把左右节点的不同遍历结果分开。

比如 preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]

去除当前元素 1 后，变成 preorder = [2,4,5,3,6,7], postorder = [4,5,2,6,7,3]

则 preorder 的第一个元素 2 是左子树的根，以此划分后序 postorder，故 4，5，2 是左子树的节点，剩下 6，7，3 是右子树的节点，以此分离开后，再以同样的方式计算孩子节点即可。

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

/**
 * 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:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        if (pre.empty()){
            return nullptr;
        }
        if (pre.size()==1){
            return new TreeNode(pre[0]);
        }

        vector<int> leftPre,leftPost,rightPre,rightPost;
        int i;
        TreeNode* root=new TreeNode(pre[0]);

        for (i=pre.size()-1;i>0;i--){
            if (pre[i]==post[post.size()-2]) {
                break;
            }
        }

        leftPre={pre.begin()+1,pre.begin()+i};
        rightPre={pre.begin()+i,pre.end()};
        leftPost={post.begin(),post.begin()+post.size()-pre.size()+i-1};
        rightPost={post.begin()+post.size()-pre.size()+i-1,post.end()-1};

        root->left=constructFromPrePost(leftPre,leftPost);
        root->right=constructFromPrePost(rightPre,rightPost);

        return root;
    }
};

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

题意

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

分析

中序遍历的结果是：左根右

后序遍历的结果是：左右根

当前节点，根据后序遍历的尾元素建立，然后将左右孩子节点的遍历结果拆分。

拆分方式如下：

根据后序最后一个元素作为根，然后去中序遍历查找根，之前的元素为左孩子，右边的为右孩子。

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

/**
 * 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:
    TreeNode* buildTree(vector<int>& in, vector<int>& post) {
        if (in.empty()){
            return nullptr;
        }
        if (in.size()==1){
            return new TreeNode(in[0]);
        }

        vector<int> leftIn,leftPost,rightIn,rightPost;
        int i;
        TreeNode* root=new TreeNode(post[post.size()-1]);

        for (i=0;i<in.size();i++){
            if (in[i]==post[post.size()-1]){
                break;
            }            
        }

        leftIn={in.begin(),in.begin()+i};
        rightIn={in.begin()+i+1,in.end()};        
        leftPost={post.begin(),post.begin()+i};        
        rightPost={post.begin()+i,post.end()-1};

        root->left=buildTree(leftIn,leftPost);
        root->right=buildTree(rightIn,rightPost);

        return root;
    }
};

114. 二叉树展开为链表

题意

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树先序遍历顺序相同。

新树

直接前序遍历，然后遍历的时候在右子树新建节点即可。

/**
 * 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 {
    TreeNode *now;
    TreeNode *head;

public:
    void flatten(TreeNode* root) {
        if (!root){
            return;
        }
        head=new TreeNode();
        now=head;
        pre(root);
        *root=*(head->right);
    }

    void pre(TreeNode* root){
        if (!root){
            return;
        }

        now->right=new TreeNode(root->val);
        now=now->right;
        pre(root->left);
        pre(root->right);
    }
};

时间复杂度： $O (n)$ ，空间复杂度： $O (n)$

原地

新建树非常好理解，但空间复杂度有点高，我们也可以原地实现，基本思想就是前序的逆序+头插法。

比如 1，2，3，4，5 的树，前序就是 1,2,4,5,3，而逆序则是 3,5,4,2,1.即

dfs(root->right)
dfs(root->left)
cout<<root->val<<endl;

的输出就是 3，5，4，3，1.

假设某个时刻之前的节点已经建立好，并且头指针为 pre，当前节点为 root，要头插，故直接 root→right=pre,pre=root 即可，只是这题同时左节点记得置空，不然会有问题。

/**
 * 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 {
    TreeNode *pre;
public:
    void flatten(TreeNode* root) {
        if (!root){
            return;
        }
        flatten(root->right);
        flatten(root->left);
        root->right=pre;
        root->left=nullptr;
        pre=root;
    }
};

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

题意

有序链表转 BST

分析

先转数组

先转成数组，然后按照 108 题的方法构建。转成数组的主要目的就是减少寻找中间节点的时间。

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        vector<int> nums;
        while(head){
            nums.push_back(head->val);
            head=head->next;
        }
        return sortedArrayToBST(nums);
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.empty()){
            return nullptr;
        }
        
        TreeNode*root=new TreeNode(nums[nums.size()/2]);
        vector<int> l={nums.begin(),nums.begin()+nums.size()/2};
        vector<int> r={nums.begin()+nums.size()/2+1,nums.end()};

        root->left=sortedArrayToBST(l);
        root->right=sortedArrayToBST(r);

        return root;
    }    
};

时间复杂度： $O (n)$ ,空间复杂度： $O (n)$

直接转

和转换为数组差不多，找中间节点作为根，前后分别作为左右。找中间节点的方法即双指针。

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

时间复杂度： $O (n)$ ,空间复杂度： $O (l o g n)$

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

题意

根据升序数组建立 BST

分析

要建立 BST，显然需要平衡，即左右子树的高度要尽可能近，那么选取根节点时，就要使得左右节点尽可能一样多。故选取中点作为根，左右作为孩子节点即可。

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

/**
 * 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:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.empty()){
            return nullptr;
        }
        
        TreeNode*root=new TreeNode(nums[nums.size()/2]);
        vector<int> l={nums.begin(),nums.begin()+nums.size()/2};
        vector<int> r={nums.begin()+nums.size()/2+1,nums.end()};

        root->left=sortedArrayToBST(l);
        root->right=sortedArrayToBST(r);

        return root;
    }
};

1008. 前序遍历构造二叉搜索树

题意

前序构造 BST

分析

BST 中序是有序的，故对前序排序就是中序，然后就变成 105 题了

105，1008，449 基本一个题

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

/**
 * 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:
    TreeNode* bstFromPreorder(vector<int>& pre) {
        vector<int> in(pre.size());
        copy(pre.begin(),pre.end(),in.begin());
        sort(in.begin(),in.end());
        return  buildTree(pre,in);
    }

    TreeNode* buildTree(vector<int>& pre, vector<int>& in) {        
        return buildNode(pre,0,pre.size()-1,in,0,in.size()-1);
    }

    TreeNode* buildNode(vector<int>& pre,int pbegin,int pend, vector<int>& in,int ibegin,int iend) {
        if (pbegin>pend||ibegin>iend||pend<0||iend<0){
            return nullptr;
        }

        TreeNode *root=new TreeNode(pre[pbegin]);
        int index;

        for (int i=ibegin;i<iend;i++){
            if (in[i]==pre[pbegin]){
                index=i;
                break;
            }
        }

        root->left=buildNode(pre,pbegin+1,pbegin+index-ibegin,in,ibegin,index-1);
        root->right=buildNode(pre,pbegin+index-ibegin+1,pend,in,index+1,iend);

        return root;
    }    
};

1028. 从先序遍历还原二叉树

题意

从先序遍历还原二叉树

分析

类似于 291 题，只是那题先序遍历时，节点为空也记录在内，而这题不记录，而是使用节点的深度来代替。

因此，在前序遍历的时候，我们要带上深度，然后判断当前节点是不是当前深度的即可。

效率

时间复杂度： $O (n)$

空间复杂度： $O (l o g n)$

代码

class Solution {
public:
    TreeNode *recoverFromPreorder(string s) {
        return get(s, 0);
    }

    TreeNode *get(string &s, int depth) {
        if (s.empty()) {
            return nullptr;
        }

        int i = 0;
        while (i < s.size() && s[i] == '-') {
            i++;
        }

        string n;
        int j = i;
        while (j < s.size() && s[j] != '-') {
            n.push_back(s[j]);
            j++;
        }
        if (i != depth) {
            return nullptr;
        }

        s = s.substr(j, s.size() - j);

        TreeNode *root = new TreeNode(stoi(n));
        root->left = get(s, i+1);
        root->right = get(s, i+1);

        return root;
    }
};

序列化

序列化的题是指将二叉树转换为一定规则的字符串

list

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

题意

序列化和反序列化二叉树

分析

序列化：直接先序遍历，遇到 null 则写入 n 即可

反序列化：同样先序遍历，当前节点处，则取值创建节点，然后去掉该值，再同样创建左右孩子节点

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Codec {
public:
    string serialize(TreeNode *root) {
        if (!root) {
            return "n";
        }
        string res;

        res.append(to_string(root->val));
        res.append(" ");
        res.append(serialize(root->left));
        res.append(" ");
        res.append(serialize(root->right));
        res.append(" ");

        return res;
    }

    TreeNode *deserialize(string data) {
        return get1(data);
    }

    TreeNode *get1(string &data) {
        if (data.empty()) {
            return nullptr;
        }
        if (data[0] == 'n') {
            data.erase(data.begin());
            while (*data.begin() == ' ') {
                data.erase(data.begin());
            }
            return nullptr;
        }

        string t;
        int i;
        for (i = 0; i < data.size(); i++) {
            if (data[i] == '-' || (data[i] >= '0' && data[i] <= '9')) {
                t.push_back(data[i]);
                continue;
            }
            break;
        }

        auto root = new TreeNode(stoi(t));

        while (i < data.size() && data[i] == ' ') {
            i++;
        }

        data = data.substr(i, data.size() - i);
        root->left = get1(data);
        root->right = get1(data);

        return root;
    }
};

449. 序列化和反序列化二叉搜索树

题意

序列化和反序列化 BST

分析

BST 也是普通的二叉树，故可以用 297 题的方法，直接序列化。但是这样没有利用到 BST 的有序性。

实际上，我们知道可以用前中后序中任意两个构造二叉树，而对于 BST，中序是一个有序的数列，即，随便给定前序或后序，只要排个序就是中序了。

故，我们只需序列化为前序或后序，反序列化时再排序，就可以构建了。

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

普通方式

class Codec {
public:
    string serialize(TreeNode *root) {
        if (!root) {
            return "n";
        }
        string res;

        res.append(to_string(root->val));
        res.append(" ");
        res.append(serialize(root->left));
        res.append(" ");
        res.append(serialize(root->right));
        res.append(" ");

        return res;
    }

    TreeNode *deserialize(string data) {
        return get1(data);
    }

    TreeNode *get1(string &data) {
        if (data.empty()) {
            return nullptr;
        }
        if (data[0] == 'n') {
            data.erase(data.begin());
            while (*data.begin() == ' ') {
                data.erase(data.begin());
            }
            return nullptr;
        }

        string t;
        int i;
        for (i = 0; i < data.size(); i++) {
            if (data[i] == '-' || (data[i] >= '0' && data[i] <= '9')) {
                t.push_back(data[i]);
                continue;
            }
            break;
        }

        auto root = new TreeNode(stoi(t));

        while (i < data.size() && data[i] == ' ') {
            i++;
        }

        data = data.substr(i, data.size() - i);
        root->left = get1(data);
        root->right = get1(data);

        return root;
    }
};

利用中序遍历有序性

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    string serialize(TreeNode* root) {
        string res=get(root);
        // cout<<res<<endl;
        return res;
    }

    string get(TreeNode* root) {
        if (!root){
            return "";
        }
        string res;
        
        res.append(to_string(root->val));
        res.append(" ");
        res.append(get(root->left));
        res.append(" ");
        res.append(get(root->right));
        res.append(" ");

        return res;
    }

    TreeNode* deserialize(string data) {
        vector<int> pre,in;
        string s;

        for (auto i:data){
            if (i>='0'&&i<='9'){
                s.push_back(i);
                continue;
            }
            if (!s.empty()){
                // cout<<s<<endl;
                pre.push_back(stoi(s));
                s.clear();
            }
        }

        in.resize(pre.size());
        copy(pre.begin(),pre.end(),in.begin());
        sort(in.begin(),in.end());

        return buildTree(pre,in);
    }

    TreeNode* buildTree(vector<int>& pre, vector<int>& in) {        
        return buildNode(pre,0,pre.size()-1,in,0,in.size()-1);
    }

    TreeNode* buildNode(vector<int>& pre,int pbegin,int pend, vector<int>& in,int ibegin,int iend) {
        if (pbegin>pend||ibegin>iend||pend<0||iend<0){
            return nullptr;
        }

        TreeNode *root=new TreeNode(pre[pbegin]);
        int index;

        for (int i=ibegin;i<iend;i++){
            if (in[i]==pre[pbegin]){
                index=i;
                break;
            }
        }

        root->left=buildNode(pre,pbegin+1,pbegin+index-ibegin,in,ibegin,index-1);
        root->right=buildNode(pre,pbegin+index-ibegin+1,pend,in,index+1,iend);

        return root;
    }    
};

655. 输出二叉树

题意

在一个 m*n 的二维字符串数组中输出二叉树:

分析

获取树高
建立结果矩阵
前序遍历，然后计算坐标填入

坐标暂时不会算

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
    vector<vector<string>> res;

public:
    vector<vector<string>> printTree(TreeNode* root) {
        int m=getHigh(root);
        int n=(1<<m)-1;
        
        while(m--){
            vector<string> t(n);
            res.push_back(t);
        }

        dfs(root,0,0,n);

        return res;
    }

    void dfs(TreeNode *root,int row,int l,int r){
        if (!root){
            return;
        }

        int mid=(r-l)/2+l;

        res[row][mid]=to_string(root->val);

        dfs(root->left,row+1,l,mid-1);
        dfs(root->right,row+1,mid+1,r);
    }

    int getHigh(TreeNode *root){
        if (!root){
            return 0;
        }

        return max(getHigh(root->left),getHigh(root->right))+1;
    }
};

606. 根据二叉树创建字符串

题意

你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。

分析

这题重点在于读题

如果 root 左右子节点都不存在，则返回 root

如果 root 左右子节点都存在，则返回 root(left)(right)

如果 root 只有左节点存在，则返回 root(left)

如果 root 只有右节点存在，则返回 root()(right)

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
    string res;

public:
    string tree2str(TreeNode* root) {
        pre(root);
        return res;    
    }

    void pre(TreeNode *root) {
        if (!root){
            return;
        }

        res.append(to_string(root->val));
        
        if (!root->left && !root->right){
            return;
        }

        res.append("(");
        pre(root->left);
        res.append(")");
        
        if (!root->right){
            return;
        }
        res.append("(");
        pre(root->right);
        res.append(")");
    }
};

求二叉树属性

二叉树的属性题，是指求二叉树中各个节点值等，比如求某层的节点值，求某处的叶子值等等

list

104. 二叉树的最大深度

题意

给定一个二叉树，找出其最大深度。

分析

可以使用层序遍历，然后每层记录深度。也可以后序遍历，取左右子树深度的最大值，然后加本层 1即可。

效率

时间复杂度： $O (n)$

空间复杂度： $O (l o g n)$

代码

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

559. N 叉树的最大深度

题意

给定一个 N 叉树，找到其最大深度。

分析

原理同 104，后序遍历，先求各子树高度，然后取最大值再加1

效率

时间复杂度： $O (n)$

空间复杂度： $O (l o g n)$

代码

class Solution {
public:
    int maxDepth(Node* root) {
        if (!root){
            return 0;
        }

        int res=0;
        for (auto i:root->children){
            res=max(res,maxDepth(i));
        }

        return res+1;        
    }
};

111. 二叉树的最小深度

题意

给定一个二叉树，找出其最小深度。

分析

原理同 104，先求各子树高度，然后取最小值再加1，但是，由于深度的定义，即到叶子节点的节点数，但是退化到链表后，深度就不是 1 了，因为根不是叶子节点，故，需要进行特判一下，排序链表这种情况。

效率

时间复杂度： $O (n)$

空间复杂度： $O (l o g n)$

代码

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root){
            return 0;
        }
        int l=minDepth(root->left);
        int r=minDepth(root->right);

        if (l==0||r==0){
            return max(l,r)+1;
        }

        return min(l,r)+1;
    }
};

404. 左叶子之和

题意

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

分析

这题关键点在于判断是不是左叶子，即如果到来叶子节点再判断，显然是不行的，因为叶子节点左右孩子都是空，所以要在左叶子父亲处判断。

这题可以前序也可以后序，后序要好理解一些，即先获取左右子树的个数，再判断当前是不是满足，最后加起来即可。

效率

时间复杂度： $O (n)$

空间复杂度： $O (1)$

代码

前序

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

后序

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

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

题意

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

分析

最简单的自然是遍历一遍了，然后直接统计即可。但这样没有利用到完全二叉树这个条件。

所谓的完全二叉树，即叶子节点必然在同一层，且一定是最左边的。那么对于里面任意一个节点来说，它的左右子树一定一个是完全二叉树，一个是满二叉树。

假设满二叉树高度为 h，则节点总数为 $O (2^{h})$ ，故我们可以利用这一点，每次判断左右子树哪个是满二叉树，则这个子树就不用遍历了，直接计算即可，而另一个子树则同样的方式展开。

问题怎么判断哪个子树是满二叉树呢？

这个简单，判断左右子树最左边的高度是否相等即可，画画图就理解了。

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

普通遍历一遍

class Solution {
    int res=0;

public:
    int countNodes(TreeNode* root) {
        if (!root){
            return 0;
        }
        res++;
        countNodes(root->left);
        countNodes(root->right);
        return res;
    }
};

完全二叉树性质

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (!root){
            return 0;
        }

        int l=getDepth(root->left);
        int r=getDepth(root->right);

        if (l==r){
            return (1<<l)+countNodes(root->right);
        }
        return (1<<r)+countNodes(root->left);
    }

    int getDepth(TreeNode *root){
        int level=0;
        
        while(root){
            root=root->left;
            level++;
        }
        
        return level;
    }
};

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

题意

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

分析

要得到每一层的最大值，就需要得到每一层的所有数据，则可以按层序来遍历，或者 dfs 时传深度，再用有序数据结构 set 来维护即可

优化

没必要用 set 来维护，直接存最值即可

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

层序遍历

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {        
        queue<TreeNode*> q;
        vector<int> res;

        q.push(root);

        while(root && !q.empty()){
            int size=q.size();
            int m=INT_MIN;                

            while(size--){
                auto t=q.front();
                q.pop();
                m=max(m,t->val);
                
                if (t->left){
                    q.push(t->left);
                }
                if (t->right){
                    q.push(t->right);
                }
            }

            res.push_back(m);
        }

        return res;
    }   
};

dfs

class Solution {    
    map<int,set<int,greater<>>> m;

public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> res;

        dfs(root,0);

        for (auto i:m){
            res.push_back((*((i.second).begin())));
        }

        return res;
    }

    void dfs(TreeNode *root,int level){
        if (!root){
            return;
        }

        m[level].insert(root->val);

        dfs(root->left,level+1);
        dfs(root->right,level+1);
    }
};

直接存最值

class Solution {    
    map<int,int> m;

public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> res;

        dfs(root,0);

        for (auto i:m){
            res.push_back(i.second);
        }

        return res;
    }

    void dfs(TreeNode *root,int level){
        if (!root){
            return;
        }

        if (m.count(level)==0){
            m[level]=INT_MIN;
        }
        m[level]=max(m[level],root->val);

        dfs(root->left,level+1);
        dfs(root->right,level+1);
    }
};

513. 找树左下角的值

题意

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

分析

层序遍历
每次更新为一层的第一个节点

优化

也可以不分层次，从右往左遍历，最后一个就是答案

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int res=root->val;

        while(root && !q.empty()){
            int size=q.size();

            res=q.front()->val;
            
            while(size--){
                auto t=q.front();
                q.pop();
                
                if (t->left){
                    q.push(t->left);
                }
                if (t->right){
                    q.push(t->right);
                }
            }
        }

        return res;
    }
};

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);

        while(root && !q.empty()){
            root=q.front();
            q.pop();
            
            if (root->right){
                q.push(root->right);
            }
            if (root->left){
                q.push(root->left);
            }
        }

        return root->val;
    }
};

662. 二叉树最大宽度

题意

求二叉树最大宽度

分析

首先要搞清楚宽度定义：每一层最左右两非 null 的节点，之间的节点数（之间 null 节点也要算）

由于宽度是在层上的定义，故可以用层序来做，对于每一层，要点就是找到最左右两非 null 的节点，问题在于怎么找。

层序当前队列中就是当前层中非 null 的节点个数，所以左右两节点还是好找，但是中间的节点数怎么算呢？中间 null 节点靠数个数是会出问题的。

所以，我们可以换一种计算方式。由于题目说，该数和完全二叉树结构相同，所以我们可以按完全二叉树给节点标坐标的方式，给每个节点标坐标，然后找到左右两节点后，直接相减即可。

当前坐标为 p，则左孩子为 2p，右孩子为 2p+1.

除了使用层序，dfs 的方式也能做，我们遍历时，只要找到当前这个节点，这一层中，最左边的节点坐标即可。

这需要两个信息：

层数
最左边的节点左边

故我们遍历时可以把层数带上，然后开一个哈希表记录层数 → 该层最左边的节点即可。那最左边的节点怎么求呢？

在 dfs 中，只要先访问左孩子再访问右孩子，那么该层访问的第一个节点必然是左节点。故判断 level 是否已经映射就能判断。

这题需要注意很坑的一点，就是坐标的范围问题，这题给定 case 有的很大，需要 unsigned long long 才能放得下。

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

bfs

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        unsigned long long res=0;
        queue<pair<TreeNode*,unsigned long long>> q;
        q.push({root,0});

        while(root&&!q.empty()){
            unsigned long long l=0;
            unsigned long long r=0;
            int size=q.size();

            for (int i=0;i<size;i++){
                auto t=q.front();
                q.pop();
                TreeNode *n=t.first;
                unsigned long long p=t.second;
                
                if (i==0){
                    l=p;
                }
                if (i==size-1){
                    r=p;
                }

                if (n->left){
                    q.push({n->left,2*p});
                }
                if (n->right){
                    q.push({n->right,2*p+1});
                }
            }

            res=max(res,r-l+1);
        }

        return res;
    }
};

dfs

class Solution {
    // level -> leftPosition
    unordered_map<int,unsigned long long> m;
    unsigned long long res=0;

public:
    int widthOfBinaryTree(TreeNode* root) {
        dfs(root,0,0);
        return res;
    }

    void dfs(TreeNode *root,int level,unsigned long long p) {
        if (!root){
            return;
        }

        if (m.count(level)==0){
            m[level]=p;
        }

        res=max(res,p-m[level]+1);

        dfs(root->left,level+1,2*p);
        dfs(root->right,level+1,2*p+1);
    }
};

199. 二叉树的右视图

题意

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

分析

要得到每一层最右边的数，最简单自然是层序遍历，直接取即可。也可以 dfs，不过需要考虑层数，故带上层数遍历，再开一个 map 从层序映射到值，每次更新，最后一次更新就是最右的值。

可以直接用 map 自动就维护 level 的顺序了，不用再排序.

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

bfs

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        vector<int> res;

        while(root&&!q.empty()){
            int size=q.size();
            
            while(size--){
                auto t=q.front();
                q.pop();
                if (size==0){
                    res.push_back(t->val);
                }

                if (t->left){
                    q.push(t->left);
                }
                if (t->right){
                    q.push(t->right);
                }
            }
        }

        return res;
    }
};

dfs

class Solution {
    map<int,int> m;

public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        pre(root,0);
        for (auto i:m){
            res.push_back(i.second);
        }
        return res;
    }

    void pre(TreeNode *root,int level){
        if (!root){
            return;
        }
        m[level]=root->val;
        pre(root->left,level+1);
        pre(root->right,level+1);
    }
};

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

题意

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

分析

如果是 BST，要求公共祖先，还可以利用大小来判断，但是如果是任意的二叉树，则不能这么做了。

最简单的，自然是开一个哈希表，把 p 到祖先节点路径全部标红，然后 q 再遍历到祖先节点，只要遇到红节点，那么自然这个节点就是相交节点。因此，我们需要遍历找到每个节点的父节点，再寻找即可。

而还有一种方法，即直接寻找，要寻找祖先节点，自然最好是从底往上找了，那么哪种遍历方式满足这一点呢？

显然是后序遍历。

那么什么时候，才会存在公共祖先节点呢？显然，是 p 和 q 分别在左右两个节点。

现在我们再来分析一下这个函数的作用

TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {

传入当前节点 root，和要寻找的两个节点 p，q 这好理解。那么返回值是什么？p 和 q 的公共祖先节点？

不，我们返回 root 子节点是否存在 p 和 q 节点。

如果 root 孩子节点存在 p，则返回 p，存在 q，则返回 q，如果都存在，那么就要看 p 和 q 是不是在一个子树上了。

上面的逻辑如下

        if (!root){
            return nullptr;
        }
        if (root==p){
            return p;
        }
        if (root==q){
            return q;
        }

现在再来看左右子树的情况

        auto l=lowestCommonAncestor(root->left,p,q);
        auto r=lowestCommonAncestor(root->right,p,q);

如果左右子树都不存在 p 和 q，即 l 和 r 都为 nullptr，自然没有公共祖先。

        if (!l&&!r){
            return nullptr;
        }

如果左子树为空，那么 p 或 q 就肯定在右子树

        if (!l){
            return r;
        }

如果右子树为空，那么 p 或 q 就肯定在左子树

        if (!r){
            return l;
        }

如果左右子树都不为空，则说明 p 和 q 一个在左一个在右，那么 root 自然就是公共祖先节点了

return root

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

map

class Solution {
    // node -> fatherNode
    unordered_map<TreeNode *, TreeNode *> m;
    unordered_map<TreeNode *, bool> visited;
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        m[root] = nullptr;
        get(root);

        while (p) {
            visited[p] = true;
            p = m[p];
        }

        while (q) {
            if (visited[q]) {
                return q;
            }
            q = m[q];
        }

        return nullptr;
    };

    void get(TreeNode *root) {
        if (!root) {
            return;
        }
        if (root->left) {
            m[root->left] = root;
        }
        if (root->right) {
            m[root->right] = root;
        }
        get(root->left);
        get(root->right);
    }
};

后序遍历

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root){
            return nullptr;
        }
        if (root==p){
            return p;
        }
        if (root==q){
            return q;
        }

        auto l=lowestCommonAncestor(root->left,p,q);
        auto r=lowestCommonAncestor(root->right,p,q);

        if (!l&&!r){
            return nullptr;
        }
        if (!l){
            return r;
        }
        if (!r){
            return l;
        }
        return root;    
    }
};

637. 二叉树的层平均值

题意

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

分析

直接 dfs 或者 bfs，把每个元素放到对应层的和中，最后求平均值即可

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
    map<int,double> m;
    unordered_map<int,int> cnt;

public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> res;

        pre(root,0);

        for (auto i=m.begin();i!=m.end();i++){           
            res.push_back((*i).second/cnt[(*i).first]);
        }

        return res;    
    }

    void pre(TreeNode *root,int level) {
        if (!root){
            return;
        }

        m[level]+=root->val;
        cnt[level]++;
        pre(root->left,level+1);
        pre(root->right,level+1);
    }
};

563. 二叉树的坡度

题意

给你一个二叉树的根节点 root ，计算并返回 整个树 的坡度。

分析

开全局变量记录结果，然后 dfs 遍历，对每个节点求坡度，再然后以这个节点为根的树的和即可

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
    int res=0;
public:
    int findTilt(TreeNode* root) {
        pre(root);
        return res;
    }

    int pre(TreeNode *root){
        if (!root){
            return 0;
        }

        int l=pre(root->left);
        int r=pre(root->right);

        res+=(abs(r-l));

        return l+r+root->val;
    }
};

652. 寻找重复的子树

题意

给定一棵二叉树 root，返回所有重复的子树。

分析

对所有子树进行序列化，然后在哈希表中查找

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
    unordered_map<string,int> m;
    vector<TreeNode*> res;

public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {

        pre(root);

        return res;
    }

    string pre(TreeNode *root){
        if (!root){
            return "#";
        }
        string s=to_string(root->val)+","+pre(root->left)+pre(root->right);
        
        if (m[s]==1){
            res.push_back(root);
        }

        m[s]++;

        return s;
    }
};

二叉树验证

二叉树验证题，主要是验证两个树的关系

list

100. 相同的树

题意

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

分析

要判断两颗树是否相同，自然方法就是遍历，然后对比每一个节点处是否相同。

可以 dfs，也可以 bfs

dfs 直接前序，先比较当前节点是否相同，只有两节点都存在且值相等，或都不存在才相同。然后左右子树都分别展开判断即可。

而 bfs 也很简单，直接开队列一层层的比较，比较每个不为空的节点即可，也可以放到一个队列中。需要注意的是，放入左右孩子和取出的顺序要一直，可以先放完一个节点的，也可以先放两个节点的左孩子。

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

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

class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        queue<TreeNode *> qu;
        qu.push(p);
        qu.push(q);

        while (!qu.empty()) {
            TreeNode *i = qu.front();
            qu.pop();
            TreeNode *j = qu.front();
            qu.pop();

            if (!i && !j) {
                continue;
            }
            if (!j || !i || (i->val != j->val)) {
                return false;
            }

            qu.push(i->left);
            qu.push(j->left);
            qu.push(i->right);
            qu.push(j->right);
        }

        return true;
    }
};

101. 对称二叉树

题意

给你一个二叉树的根节点 root ，检查它是否轴对称。

分析

要检查是否轴对称，即检查左右子树是否对称，而这类似于 100，只是 100 是检查两树是否相等，而这是检查是否对称。

只需简单改动 100 题中比对的节点即可，即 p→left 和 q→right，p→right 和 q→left 相等。

可以 dfs，也可 bfs

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

dfs

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root){
            return true;
        }
        return isSameTree(root->left,root->right);
    }

    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->right)&&isSameTree(p->right,q->left);
    }    
};

bfs

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root){
            return true;
        }
        return isSameTree(root->left,root->right);
    }

    bool isSameTree(TreeNode *p, TreeNode *q) {
        queue<TreeNode *> qu;
        qu.push(p);
        qu.push(q);

        while (!qu.empty()) {
            TreeNode *i = qu.front();
            qu.pop();
            TreeNode *j = qu.front();
            qu.pop();

            if (!i && !j) {
                continue;
            }
            if (!j || !i || (i->val != j->val)) {
                return false;
            }

            qu.push(i->left);
            qu.push(j->right);
            qu.push(i->right);
            qu.push(j->left);
        }

        return true;
    }    
};

110. 平衡二叉树

题意

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过 1，那么它就是一棵平衡二叉树。

分析

平衡二叉树即左右子树高度之差不超过 1 的树，那么这题就是 104 题求树高度的一个应用题，只需我们再递归求树高度时，拿到左右子树的高度，然后判断差的情况即可.

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
    bool res=true;

public:
    bool isBalanced(TreeNode* root) {
        get(root);
        return res;    
    }

    int get(TreeNode *root){
        if (!root){
            return true;
        }

        int l=get(root->left);
        int r=get(root->right);

        if (abs(l-r)>1){
            res=false;
        }

        return max(l,r)+1;
    }
};

98. 验证二叉搜索树

题意

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

分析

由于 BST 的有序特性，故，我们只需利用这一点即可。而 BST 中序遍历后是升序的，所以这题本质上其实是考中序遍历。

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

递归

class Solution {
    vector<int> nums;

public:
    bool isValidBST(TreeNode* root) {
        in(root);

        for (int i=1;i<nums.size();i++){
            if (nums[i-1]>=nums[i]){
                return false;
            }
        }

        return true;
    }

    void in(TreeNode *root){
        if (!root){
            return; 
        }

        in(root->left);
        nums.push_back(root->val);
        in(root->right);
    }
};

迭代

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> s;
        long pre=LONG_MIN;
        
        while(root || !s.empty()){
            while(root){
                s.push(root);
                root=root->left;
            }
            root=s.top();
            s.pop();
            if (pre>=root->val){
                return false;
            }
            pre=root->val;
            root=root->right;            
        }

        return true;
    }
};

958. 二叉树的完全性检验

题意

给定一个二叉树的 root ，确定它是否是一个 完全二叉树 。

分析

要验证是否是完全二叉树，得首先知道完全二叉树的性质，完全二叉树，即左右叶子节点都在最底层，且都在最左边。

换句话说，主要就是判断叶子节点是不是在一层，且是不是在最左边，如果是 dfs 的话，就比较麻烦，层序一层一层的遍历更加方便。

故直接层序遍历，然后对于每一层，如果出现了一次 null，则后面必须全为 null，不然就不是完全二叉树。

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        queue<TreeNode*> q;
        bool flag=false;
        q.push(root);

        while(root && !q.empty()){
            int size=q.size();
            
            for (int i=1;i<size+1;i++){
                auto n=q.front();
                q.pop();

                if (!n){
                    flag=true;
                    continue;    
                }
                
                if (flag){
                    return false;
                }

                q.push(n->left);
                q.push(n->right);
            }
        }

        return true;
    }
};

993. 二叉树的堂兄弟节点

题意

判断 x 和 y 是否是堂兄弟

分析

所谓堂兄弟，就是指两节点在同一层，且父亲不同。故，我们要获取 x 和 y 的层数以及父节点。

可以 dfs，由于没有重复元素，直接根据值寻找即可，只是要带上层数。bfs 也行，这样就不用判断层数，只是要判断父节点是否相同，故可以带上节点的坐标。

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

dfs

class Solution {
    int xdepth,ydepth,xparent,yparent;

public:
    bool isCousins(TreeNode* root, int x, int y) {
        xparent=-1;
        yparent=-1;

        get(root,0,x,y);

        return (xdepth==ydepth)&&(xparent!=-1)&&(yparent!=-1)&&(xparent!=yparent);
    }

    void get(TreeNode *root,int level,int x,int y) {
        if (!root){
            return;
        }

        if ((root->left && root->left->val==x )||(root->right&&root->right->val==x)){
            xparent=root->val;
            xdepth=level;
        }
        if ((root->left && root->left->val==y )||(root->right&&root->right->val==y)){
            yparent=root->val;
            ydepth=level;
        }

        get(root->left,level+1,x,y);
        get(root->right,level+1,x,y);
    }
};

bfs

class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        queue<pair<TreeNode*,int>> q;
        q.push({root,1});

        while(root && !q.empty()){
            int size=q.size();     
            bool xf=false;  
            int xp=-1;     
            bool yf=false;       
            int yp=-1;

            while(size--){
                auto t=q.front();
                q.pop();

                if (t.first->val==x){
                    xf=true;
                    xp=t.second/2;
                }
                if (t.first->val==y){
                    yf=true;
                    yp=t.second/2;
                }

                if (t.first->left){
                    q.push({t.first->left,2*t.second});
                }                
                if (t.first->right){
                    q.push({t.first->right,2*t.second+1});
                }
            }

            if (xf && yf && (xp!=-1) && (yp!=-1) && (xp!=yp)){
                return true;
            }
        }

        return false;
    }
};

剑指 Offer 26. 树的子结构

题意

输入两棵二叉树 A 和 B，判断 B 是不是 A 的子结构

分析

B 如果是 A 的子结构，要么 A 、B 相等，要么 B 和 A 的左子树相等，要么和 A 的右子树相等。

而判断两树相等，类似于 100 题的做法，直接遍历判断每个节点即可，只是这题要多一点，如果当前节点 B 为空，那么 A 无论有没有节点，都是相同的。

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
public:
    bool isSubStructure(TreeNode* a, TreeNode* b) {
        if (!a || !b){
            return false;
        }
        return equal(a,b) || isSubStructure(a->left,b) || isSubStructure(a->right,b);
    }

   bool equal(TreeNode *a,TreeNode *b) {
        if (!b){
            return true;
        }
        if (!a) {
            return false;
        }        
        if (a->val != b->val){
            return false;
        }
        return equal(a->left,b->left) && equal(a->right, b->right);
    }      
};

二叉树修改

修改题就是涉及到树形状的修改，后序用得比较多

list

226. 翻转二叉树

题意

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

分析

可以 dfs 或 bfs，基本原理就是，遍历节点，然后交换这个节点的左右孩子即可。

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

dfs

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root){
            return nullptr;
        }

        auto t=root->left;
        root->left=root->right;
        root->right=t;

        invertTree(root->left);
        invertTree(root->right);

        return root;
    }
};

bfs

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);

        while(root && !q.empty()){
            int size=q.size();
            
            while(size--){
                auto t=q.front();
                q.pop();

                auto n=t->left;
                t->left=t->right;
                t->right=n;

                if (t->left){
                    q.push(t->left);
                }
                if (t->right){
                    q.push(t->right);
                }
            }
        }

        return root;
    }
};

617. 合并二叉树

题意

合并两二叉树

分析

同时遍历两树相同位置的节点：

如果某个节点不存在，则返回零一节点
如果两节点都存在，则第二个节点的值加到第一个节点上
然后修改第一个节点的左右子树

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        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;
    }
};

814. 二叉树剪枝

题意

给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。

返回移除了所有不包含 1 的子树的原二叉树。

分析

由于要重建树，涉及修改节点，故最好的方式就是从底往上构建。而这是典型的后序遍历过程。

故后序遍历，先假设当前节点的左右子节点都构建好了，然后如果左右子节点不为空，说明左右子节点含有 1，故返回当前节点。

如果当前节点为 0，则返回空，否则还是返回 0

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if (!root){
            return nullptr;
        }

        root->left=pruneTree(root->left);
        root->right=pruneTree(root->right);

        if (root->left || root->right){
            return root;
        }

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

        return root;
    }
};

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

题意

填充它的每个 next 指针

分析

最简单的，自然层序遍历即可，记录前指针，然后指向即可。

而这题由于是完全二叉树，所以，其实 next 指针只有两种情况：

要么是 root→left 指向 root→right
要么是 root→right 指向 root→next→left

故直接递归修改即可

效率

时间复杂度： $O (n)$

空间复杂度： $O (1)$

代码

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) {
            return nullptr;
        }
        if (root->left) {
            root->left->next=root->right;
        }
        if (root->next && root->right){
            root->right->next=root->next->left;
        }
        connect(root->left);
        connect(root->right);
        return root;
    }
};

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

题意

填充它的每个 next 指针

分析

这题比 116 要复杂一些，是任意给的二叉树，直接层序比较简单

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node *> q;
        q.push(root);
        Node *pre=nullptr;

        while(root && !q.empty()) {
            int size=q.size();
            pre=nullptr;

            while(size--){
                auto t=q.front();
                q.pop();

                if (pre){
                    pre->next=t;
                }
                pre=t;

                if (t->left){
                    q.push(t->left);
                }
                if (t->right){
                    q.push(t->right);
                }
            }
        }

        return root;
    }
};

919. 完全二叉树插入器

题意

往完全二叉树中插入节点

分析

对完全二叉树标号，最后叶子节点为 p，那么父节点为 p/2，而新节点就是该节点的子节点

故每次找到要插入的父节点即可

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class CBTInserter {
    TreeNode *head;
    int p = -1;
    int maxLevel = 0;
    unordered_map<int, TreeNode *> m;

public:
    CBTInserter(TreeNode *t) {
        head = t;
    }

    int insert(int val) {
        maxLevel = 0;
        p = -1;
        dfs(head, 0, 1);
        if (p % 2 != 0) {
            p++;
        }
        auto node = m[p / 2];
        m.clear();

        // cout << node->val << endl;

        if (!node->left) {
            node->left = new TreeNode(val);
            return node->val;
        }

        node->right = new TreeNode(val);
        return node->val;
    }

    TreeNode *get_root() {
        return head;
    }

    void dfs(TreeNode *root, int level, int pos) {
        if (!root) {
            return;
        }
        if (level >= maxLevel) {
            p = pos;
            maxLevel = level;
        }
        m[pos] = root;
        dfs(root->left, level + 1, 2 * pos);
        dfs(root->right, level + 1, 2 * pos + 1);
    }
};

二叉树的路径

二叉树的路径题

list

112. 路径总和

题意

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

分析

要看路径的和，那么直接 dfs 即可，需要注意，要判断的是 root 到叶子节点，所以必须到叶子节点的时候判断是否 targetSum 为 0.

也可以 bfs，每次往下一层走时，同时带上这个节点下面路径还需要的 targetSum，直到最后叶子节点判断是否为 0 即可。

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

dfs

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

        return l||r;
    }    
};

bfs

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        queue<pair<TreeNode*,int>> q;
        q.push({root,targetSum});
        
        while(root && !q.empty()){
            int size=q.size();

            while(size--){
                auto t=q.front();
                q.pop();

                if (!t.first->left && !t.first->right && t.second-t.first->val==0){
                    return true;
                }

                if (t.first->left){
                    q.push({t.first->left,t.second-t.first->val});
                }
                if (t.first->right){
                    q.push({t.first->right,t.second-t.first->val});
                }
            }
        }

        return false;
    }
};

113. 路径总和 II

题意

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

分析

原理同 112，只是 112 是判断存不存在，而这题则是找出所有满足的路径。

方法和 112 一样，可以 dfs 或 bfs。只是多出把路径存起来的过程。

对于 dfs，可以直接把路径信息带上，这样找到满足的叶子节点，路径信息也就找到了。

而对于 bfs，同样也可以带上路径，只是空间复杂度大了点，可以记录下每个节点的父节点，然后找到符合的叶子节点后，再回去找遍历路径即可。

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
    vector<vector<int>> res;

public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        dfs(root,targetSum,{});
        return res;
    }

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

class Solution {
    vector<vector<int>> res;
    unordered_map<TreeNode *,TreeNode *> m;

public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        queue<pair<TreeNode*,int>> q;
        q.push({root,targetSum});
        m[root]=nullptr;        
        
        while(root && !q.empty()){
            int size=q.size();

            while(size--){
                auto t=q.front();
                q.pop();

                if (!t.first->left && !t.first->right && t.second-t.first->val==0){
                    get(t.first);
                }

                if (t.first->left){
                    m[t.first->left]=t.first;
                    q.push({t.first->left,t.second-t.first->val});
                }
                if (t.first->right){
                    m[t.first->right]=t.first;
                    q.push({t.first->right,t.second-t.first->val});
                }
            }
        }

        return res;
    }

    void get(TreeNode *root){
        vector<int> t;

        while(root){
            t.push_back(root->val);
            root=m[root];
        }

        res.push_back({t.rbegin(),t.rend()});
    }
};

437. 路径总和 III

题意

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

暴力

最简单的，自然是遍历每一个节点，然后再以此为根节点向下遍历，看是否存在该路径

class Solution {
    int res=0;

public:
    int pathSum(TreeNode* root, int targetSum) {
        if (!root){
            return 0;
        }
        
        dfs(root,targetSum);
        
        pathSum(root->left,targetSum);
        pathSum(root->right,targetSum);

        return res;
    }

    bool dfs(TreeNode *root,int targetSum){
        if (!root){
            return false;
        }

        targetSum-=root->val;
        
        if (targetSum==0){
            res++;
        }

        return dfs(root->left,targetSum)|| dfs(root->right,targetSum);
    }
};

时间复杂度： $O (n^{2})$ ，空间复杂度： $O (n)$

前缀和

由于要求的路径仅是向下的，即前序遍历的过程中，是一个方向的
这题要求和为 target 的数目，其实非常类似于一维数组，然后求区间和为 target 的数目，只是这里变成了树，但是由于路径向下，实际上，我们还是可以构造前缀和的
构造前缀和后，其实就是求对于 t1,求满足要求的 t2 存在（t2=t1+target)，而这又是一个典型的存在性问题，所以可以用哈希表缓存值→个数
如果按照数组的计算的话，最容易理解的自然是要先构造出前缀和，然后再计算。当然也可以简化，边构造，边放到哈希表里，边寻找满足条件的值。
这题也是一样，我们可以边构造前缀和，边计算
对于一个节点，我们显然要知道它当前的前缀和才行，怎么办呢？最简单的，自然是把前面的和作为参数传下来
然后，我们就可以根据当前的前缀和到哈希表中寻找满足条件的个数了
但是这题还有一个难点，那就是，这是一颗树，遍历的时候不只是一个方向，而是多个方向，而且会回溯。
如果只是往下面左右走的话，还好，毕竟前面的前缀和都是一样大
但是如果要回溯呢？回溯就是从这个节点往前缀，所以，前缀和需要删去这个节点
当然，和是不用删的，毕竟作为参数传递，都在栈里的，相互不影响，但是，哈希表却是放到全局的，所以要删去一个值
然后最后还需要注意的，就是需要再最开始出添加一个 0，不然如果从根开始满足条件的那些路径会被忽略。

class Solution {
    int res=0;
    int sum;
    // presum->count
    unordered_map<int,int> m;

public:
    int pathSum(TreeNode* root, int targetSum) {
        sum=targetSum;
        m[0]=1;
        pre(root,0);
        return res;
    }  

    void pre(TreeNode *root,int presum){
        if (!root){
            return;
        }

        int cur=presum+root->val;

        res+=(m[cur-sum]);

        m[cur]++;
        pre(root->left,cur);
        pre(root->right,cur);
        m[cur]--;
    }
};

时间复杂度： $O (n)$ ，空间复杂度： $O (n)$

257. 二叉树的所有路径

题意

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

分析

要求所有路径，直接 dfs 或 bfs 即可，只是要打印路径，所以遍历的过程中要带上之前的路径。

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

dfs

class Solution {
    vector<string> res;

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        pre(root,"");
        return res;
    }

    void pre(TreeNode *root,string s) {
        if (!root){
            return;
        }

        s.append(to_string(root->val));

        if (!root->left && !root->right){
            res.push_back(s);
        }

        if (root->left || root->right){
            s.append("->");
        }

        pre(root->left,s);
        pre(root->right,s);
    }
};

bfs

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        queue<pair<TreeNode*,string>> q;
        q.push({root,""});
        vector<string> res;

        while(root && !q.empty()){
            int size=q.size();

            while(size--){
                auto t=q.front();
                q.pop();

                t.second.append(to_string(t.first->val)+"->");

                if (!t.first->left && !t.first->right){
                    t.second=t.second.substr(0,t.second.size()-2);
                    res.push_back(t.second);
                }

                if (t.first->left){
                    q.push({t.first->left,t.second});
                }
                if (t.first->right){
                    q.push({t.first->right,t.second});
                }
            }    
        }

        return res;
    }
};

543. 二叉树的直径

题意

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

分析

要求最长路径，我们先来看路径该怎么求：

经过节点 a 的最长路径该是多少？显然，应该是左边的路径长度+右边的路径长度+1

而要求整个的最大路径长度，显然，我们开个全局变量，然后遍历节点，对每个节点都更新一下即可。

那么问题来了，对于节点 a，它的路径长度该怎么求呢？前面说了，需要知道左右子树的最大路径长度。

所以，我们定义一个函数，应该求该节点下方的最大路径长度

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
    int res=0;

public:
    int diameterOfBinaryTree(TreeNode* root) {
        get(root);
        return res;
    }

// 求 root 下方的最大路径长度
    int get(TreeNode *root){
        if (!root){
            return 0;
        }
        int l=get(root->left);
        int r=get(root->right);

// 整体的最大
        res=max(res,l+r);

// 经过 root 的下方最大路径长度
        return max(l,r)+1;
    }
};

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

题意

给你一个二叉树的根节点 root ，返回其 最大路径和 。

分析

不同于 437，虽然两者都是求最大路径，但是从 437 对路径有限制，只是向下，所以可以用前缀和。而这题则对路径没有限制。

这题更类似于 543，都是求任意的最大路径，不过 543 只是求路径长度，而这题求的是所有路径上的节点和的最大值。

所以参考 543，全局开最大值，然后遍历每个节点进行更新。

遍历时，对每个节点进行操作，获取经过这个节点，下方的最大路径，然后再返回即可，需要注意的是，如果路径和小于，则不再选这个路径，所以要变成 0.

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
    int res=INT_MIN;

public:
    int maxPathSum(TreeNode *root) {
        get(root);
        return res;
    }

    // 求 root 下方的最大路径长度
    int get(TreeNode *root) {
        if (!root) {
            return 0;
        }
        int l = get(root->left);
        int r = get(root->right);

        // 整体的最大
        res = max(res, l + r + root->val);

        // 经过 root 的下方最大路径长度
        int t=max(l, r) + root->val;
        if (t<0){
            t=0;
        }
        return t;
    }
};

687. 最长同值路径

题意

给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。这条路径可以经过也可以不经过根节点。

分析

本题相对于 543，只多了一步，那就是判断左右节点是否与当前节点值相同，如果不同，则左右节点路径长度要清零。

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
    int res=0;

public:
    int longestUnivaluePath(TreeNode* root) {
        get(root);
        return res;
    }

    // 求 root 下方的最大路径长度
    int get(TreeNode *root){
        if (!root){
            return 0;
        }
        int l=get(root->left);
        int r=get(root->right);

        if (root->left && root->val != root->left->val){
            l=0;
        }
        if (root->right && root->val != root->right->val){
            r=0;
        }

        // 整体的最大
        res=max(res,l+r);

        // 经过 root 的下方最大路径长度
        return max(l,r)+1;
    }    
};

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

题意

计算从根节点到叶节点生成的 所有数字之和 。

分析

直接遍历即可，最后遍历到叶子节点再把和加到全局变量中，而由于涉及到前面的值，故遍历时需要把前面路径的和同样传递进来

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

dfs

class Solution {
    int res=0;

public:
    int sumNumbers(TreeNode* root) {
        get(root,0);
        return res;
    }

    void get(TreeNode *root,int sum){
        if (!root){
            return;
        }
        sum=sum*10+root->val;
        if (!root->left && !root->right){
            res+=sum;
        }
        get(root->left,sum);
        get(root->right,sum);
    }
};

bfs

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        int res=0;
        queue<pair<TreeNode*,int>> q;
        q.push({root,0});

        while(root && !q.empty()){
            int size=q.size();

            while(size--){
                auto t=q.front();
                q.pop();
                int n=t.second*10+t.first->val;

                if (!t.first->left && !t.first->right){
                    res+=n;
                }

                if (t.first->left){
                    q.push({t.first->left,n});
                }
                if (t.first->right){
                    q.push({t.first->right,n});
                }
            }
        }

        return res;
    }
};

988. 从叶结点开始的最小字符串

题意

给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个 [0, 25] 范围内的值，分别代表字母 'a' 到 'z'。

返回按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。

分析

直接遍历，传递前面路径信息，到了叶子节点就放到有序集合中，最后取出来即可

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
    set<string> m;

public:
    string smallestFromLeaf(TreeNode* root) {
        get(root,"");
        return *m.begin();
    }

    void get(TreeNode *root,string s){
        if (!root){
            return;
        }

        s.push_back('a'+root->val);

        if (!root->left && !root->right){
            reverse(s.begin(),s.end());
            m.insert(s);
        }
                
        get(root->left,s);
        get(root->right,s);
    }
};

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

题意

给定一个二叉树（具有根结点 root），一个目标结点 target ，和一个整数值 k 。

返回到目标结点 target 距离为 k 的所有结点的值的列表。答案可以以任何顺序返回。

分析

遍历一遍，然后记录到父节点的指针
由于有了父节点指针，所以树就变成图了
然后从目标 target 出发，直接 dfs，知道遍历深度等于所求 k（需要记录来的方向，不然会死循环）

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
    unordered_map<int,TreeNode *> m;
    int n;
    vector<int> res;

public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        m[root->val]=nullptr;
        n=k;
        dealParents(root);
        search(target,nullptr,0);
        return res;
    }

    void dealParents(TreeNode *root) {
        if (!root){
            return;
        }

        if (root->left){
            m[root->left->val]=root;
            dealParents(root->left);
        }
        if (root->right){
            m[root->right->val]=root;
            dealParents(root->right);
        }
    }

    void search(TreeNode *root,TreeNode *pre,int depth) {
        if (!root){
            return;
        }
        if (depth==n){
            res.push_back(root->val);
        }
        if (root->left!=pre) {
            search(root->left,root,depth+1);
        }
        if (root->right!=pre) {
            search(root->right,root,depth+1);
        }
        if (m[root->val]!=pre) {
            search(m[root->val],root,depth+1);
        }
    }
};

BST

二叉搜索树相关的题，主要用中序

list

700. 二叉搜索树中的搜索

题意

在 BST 中查找值

分析

这题考的就是 BST 的性质，即 left<root<right，然后直接二分即可

效率

时间复杂度： $O (n)$

空间复杂度： $O (1)$

代码

递归

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

迭代

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

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

题意

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

分析

要把每个节点转换为所有比它大的值之和，那这些节点在什么地方？

根据 BST 的性质，即它的父节点和父节点的右子树所有节点，那么，那么如果我们有一种遍历方式，先遍历这些节点，再遍历该节点，不就能求了吗？

而这，其实就是中序反过来的循序，即后中前的顺序。

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
    int sum=0;

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

剑指 Offer II 053. 二叉搜索树中的中序后继

题意

设计一个算法，找出二叉搜索树中指定节点的 “下一个” 节点（也即中序后继）。

分析

BST 中，左子树<root<右子树，而要求中序后继，即求下一个比当前节点大的元素。

如果当前节点在 left，那么下一个节点在根

如果当前节点在根，那么下一个节点在右子树

如果当前节点在右子树，那么下一个节点也在右子树

怎么判断目标节点 p 在哪里呢？很简单，和当前遍历的节点比较大小即可：

如果 p>root，说明 p 在 root 的右子树，自然 p 的下一个元素也在 root 的右子树

如果 p==root，自然 p 的下一个元素也在右子树

而如果 p<root，说明 p 在 root 的左子树，那么 p 的下一个元素可能在 root 的左子树，也可能就是 root 元素，需要先在左子树找，如果找不到就是 root

效率

时间复杂度： $O (n)$

空间复杂度： $O (1)$

代码

递归

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (!root){
            return nullptr;
        }

        if (root->val <= p->val){
            return inorderSuccessor(root->right,p);
        }

        auto n=inorderSuccessor(root->left,p);
        if (n){
            return n;
        }
        return root;
    }
};

迭代

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode *res=nullptr;

        while(root){
            if (root->val<=p->val){
                root=root->right;
                continue;
            }
            res=root;
            root=root->left;
        }

        return res;
    }
};

剑指 Offer 33. 二叉搜索树的后序遍历序列

题意

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

分析

后序遍历的结果是：左右根

BFS 的性质：左<根<右

所以，有效的数组就必然满足：最后一个元素是根，然后前面可以分为两个子数组，第一个小于根，第二个大于根。

不满足就不是 BST，然后递归即可

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
public:
    bool verifyPostorder(vector<int>& post) {
        if (post.empty()){
            return true;
        }

        int root=post[post.size()-1];
        int i=0;
        int j;

        while(i<post.size()-1 && post[i]<root){
            i++;
        }
        j=i;

        while(i<post.size()-1){
            if (post[i]<root){
                return false;
            }

            i++;
        }

        vector<int> l={post.begin(),post.begin()+i};
        vector<int> r={post.begin()+i,post.end()-1};

        return verifyPostorder(l)&&verifyPostorder(r);
    }
};

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

题意

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

分析

要在 BST 中获取差的最小值，显然需要两个数大小最接近，而 BST 的有序性质，中序的是否就是递增的，所以直接中序遍历，然后求相邻的差值最小即可

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

辅助数组

class Solution {
    vector<int> nums;

public:
    int getMinimumDifference(TreeNode* root) {
        int res=INT_MAX;
        in(root);
        for (int i=1;i<nums.size();i++){        
            res=min(res,nums[i]-nums[i-1]);
        }

        return res;
    }

    void in(TreeNode *root){
        if (!root){
            return;
        }
        in(root->left);
        nums.push_back(root->val);
        in(root->right);
    }
};

前项指针

class Solution {
    int pre=-999999;
    int res=INT_MAX;

public:
    int getMinimumDifference(TreeNode* root) {
        in(root);
        return res;
    }

    void in(TreeNode *root){
        if (!root){
            return;
        }
        in(root->left);
        res=min(res,root->val-pre);
        pre=root->val;
        in(root->right);
    }
};

栈迭代

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        stack<TreeNode *> s;
        int res=INT_MAX;
        int pre=-9999999;

        while(root || !s.empty()){
            while(root){
                s.push(root);
                root=root->left;
            }

            auto t=s.top();
            s.pop();
            res=min(res,t->val-pre);
            pre=t->val;
            root=t->right;
        }

        return res;
    }
};

230. 二叉搜索树中第 K 小的元素

题意

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k ****个最小元素（从 1 开始计数）。

分析

直接中序遍历，然后计数 k 次即可

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

迭代

class Solution {    
    int res;
    int cnt;

public:
    int kthSmallest(TreeNode* root, int k) {
        cnt=k;
        dfs(root);
        return res;
    }

    void dfs(TreeNode *root){
        if (!root) {
            return;
        }
        dfs(root->left);
        cnt--;
        if (cnt==0){
            res=root->val;
            return;
        }
        dfs(root->right);
    }
};

stack

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> s;

        while(root || !s.empty()){
            while(root){
                s.push(root);
                root=root->left;
            }

            auto t=s.top();
            s.pop();
            k--;
            if (k==0){
                return t->val;
            }
            root=t->right;
        }

        return 0;
    }
};

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

题意

给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

分析

中序的逆序即可，就变成求第 k 小了，即 230 题

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
    int res;
    int cnt;

public:
    int kthLargest(TreeNode* root, int k) {
        cnt=k;
        dfs(root);
        return res;
    }

    void dfs(TreeNode *root){
        if (!root) {
            return;
        }
        dfs(root->right);
        cnt--;
        if (cnt==0){
            res=root->val;
            return;
        }
        dfs(root->left);
    }
};

501. 二叉搜索树中的众数

题意

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

分析

对于 BST 的题，根据 BST 的性质，即中序是一个有序数组。那么基本上都可以转换成有序数组的题。

即对于这题，等价于：在有序数组中找众数

要怎么找？很简单，遍历一遍即可，相同的数都相邻，直接记录这个数的出现次数，比最大次数还大的，就是众数了。

效率

时间复杂度： $O (n)$

空间复杂度： $O (1)$

代码

class Solution {
    vector<int> res;
    int cnt=0;
    int maxCnt=0;
    int pre=INT_MIN;
    int last=INT_MIN;

public:
    vector<int> findMode(TreeNode* root) {
        in(root);
        return res;
    }

    void in(TreeNode *root){
        if (!root){
            return;
        }
        in(root->left);

        if (pre==INT_MIN||root->val==pre){
            cnt++;
        } else {
            cnt=1;
        }
        if (cnt==maxCnt && root->val!=last){
            last=root->val;
            res.push_back(root->val);
        }
        if (cnt>maxCnt){
            res.clear();
            res.push_back(root->val);
            maxCnt=cnt;
            last=root->val;
        }

        pre=root->val;
        in(root->right);
    }
};

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

题意

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

分析

根据二叉树的性质，如果 root 的值比 p 和 q 的值都大，说明 p 和 q都在左子树，如果 root 比 p 和 q 都小，则说明 p 和 q 都在右子树，否则这时 root 就是最近的公共祖先.

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root){
            return nullptr;        
        }

        if (root->val < p->val &&  root->val < q->val){
            return lowestCommonAncestor(root->right,p,q);
        }
        if (root->val > p->val && root->val > q->val){
            return lowestCommonAncestor(root->left,p,q);
        }

        return root;
    }
};

653. 两数之和 IV - 输入 BST

题意

给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

分析

直接开个哈希表，把之前遍历的元素记录起来，然后遍历到当前节点时，只要以前 k-val 元素存在，那么就满足

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
    unordered_map<int,int> m;

public:
    bool findTarget(TreeNode* root, int k) {
        if (!root){
            return false;
        }
        if (m.count(k-root->val)!=0){
            return true;
        }
        m[root->val]++;
        return findTarget(root->left,k) ||findTarget(root->right,k); 
    }
};

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

题意

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。

分析

根据 BST 的性质，直接二叉寻找插入点即可

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

递归

class Solution {
    int n;

public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root){
            return new TreeNode(val);
        }
        n=val;
        dfs(root);
        return root;
    }

    void dfs(TreeNode *root) {
        if (!root){
            return;
        }

        if (n > root->val) {
            if (!root->right){
                root->right=new TreeNode(n);
                return;
            }
            dfs(root->right);
            return;
        }

        if (!root->left){
            root->left=new TreeNode(n);
            return;
        }
        dfs(root->left);
    }
};

迭代

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {                
        if (!root){
            return new TreeNode(val);
        }

        TreeNode *tmp=root;

        while(root){
            if (val > root->val) {
                if (!root->right){
                    root->right=new TreeNode(val);
                    return tmp;
                }
                root=root->right;
                continue;
            }

            if (!root->left){
                root->left=new TreeNode(val);
                return tmp;
            }
            root=root->left;
        }

        return tmp;
    }
};

669. 修剪二叉搜索树

题意

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

分析

遍历 BST，分为这些情况：

如果当前节点 <low，说明左子树舍弃

如果当前节点 >high，说明右子树舍弃

修改左右子树

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

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

99. 恢复二叉搜索树

题意

给你二叉搜索树的根节点 root ，该树中的恰好两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

分析

这题的难点就在于怎么找到这两个节点，由于 BST 的有序特性，也就等价于，在升序数组中，怎么找到两个被交换过的数。

方法就是记录前一个节点，然后和当前节点进行比较，如果更大，则说明有问题

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
    TreeNode *pre;
    TreeNode *t1;
    TreeNode *t2;

public:
    void recoverTree(TreeNode* root) {
        in(root);
        swap(t1->val,t2->val);
    }

    void in(TreeNode *root){
        if (!root){
            return;
        }

        in(root->left);
        if (pre && pre->val > root->val){
            if (!t1){
                t1=pre;
            }
            t2=root;
        }
        pre=root;
        in(root->right);
    }
};

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

题意

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点

分析

先找到要删除的节点：

如果当前节点是叶子节点，直接删除
如果只有一个孩子，则用该孩子代替该节点
如果有两个孩子，则用当前节点的中序前继或后继代替该节点，并删除前继或后继

效率

时间复杂度： $O (n)$

空间复杂度： $O (n)$

代码

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root){
            return nullptr;
        }

        if (root->val > key){
            root->left=deleteNode(root->left,key);            
        }
        if (root->val < key){
            root->right=deleteNode(root->right,key);
        }
        if (root->val != key){
            return root;
        }

        if (!root->left && !root->right){
            return nullptr;
        }

        if (!root->left){
            return root->right;
        }
        
        if (!root->right){
            return root->left;
        }

        TreeNode *cur=root->right;
        while(cur->left){
            cur=cur->left;
        }
        root->val=cur->val;
        root->right=deleteNode(root->right,root->val);

        return root;
    }
};

总结

总的来说，二叉树的题并不难，多是中等题，并且主要依赖于各种遍历，只要遍历吃透了，那么二叉树的题就应该不是大问题。

参考

Why Red Black Trees always having nil nodes as their leaf nodes and what is it implies?

How does a red-black tree work?

从 2-3-4 树模型到红黑树实现

硬核图解红黑树并手写实现

通过2-3-4树理解红黑树

https://segmentfault.com/a/1190000039774810