【代码随想录】第8章二叉树

标签：node right return 代码随想录二叉树 TreeNode root left

第8章二叉树

1. 二叉树理论基础

二叉树种类

（1）满二叉树

【代码随想录】第8章二叉树_二叉树

（2）完全二叉树

【代码随想录】第8章二叉树_算法_02

（3）二叉搜索树

或称二叉查找树

中序遍历是递增序列

【代码随想录】第8章二叉树_算法_03

（4）平衡二叉搜索树

【代码随想录】第8章二叉树_数据结构_04

二叉树的存储方式

可以链式存储，也可以顺序存储

链式存储用指针，顺序存储用数组

顺序存储的元素在内存是连续分布的，链式存储则是通过指针把分布在散落在各个地址的结点串联在一起

【代码随想录】第8章二叉树_算法_05

【代码随想录】第8章二叉树_数据结构_06

用数组来存储二叉树如何遍历的呢？

如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

二叉树的遍历

深度优先遍历：都有递归和迭代两种方法

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

【代码随想录】第8章二叉树_算法_07

广度优先遍历

层次遍历（迭代法）

二叉树的定义

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

2. 二叉树的遍历

144. 二叉树的前序遍历

94. 二叉树的中序遍历

145. 二叉树的后序遍历

二叉树的递归遍历

递归三要素：

确定递归函数的参数和返回值：void preorder(TreeNode *root, vector<int>& res)
确定终止条件：if(cur == nullptr) return;
确定单层递归的逻辑

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

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

    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        preorder(root, res);
        return res;
    }
};

实现不同的遍历顺序通过修改单层递归的逻辑实现

二叉树的迭代遍历

通过栈实现

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

（1）前序遍历

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        if(root == nullptr)  return res;

        s.push(root);  //压入根结点
        while (!s.empty()){  //入栈是 根右左
            TreeNode* node = s.top();  s.pop();
            res.push_back(node->val);                 //中
            if (node->right) stk.push(node->right);   //右
            if (node->left)  stk.push(node->left);    //左
        }

        return res;
    }
};

（2）中序遍历

【代码随想录】第8章二叉树_数据结构_08

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* cur = root;
        
        while (cur != nullptr || !s.empty()) {
            if (cur != nullptr) {               // 指针来访问节点，访问到最底层
                s.push(cur);                    // 将访问的节点放进栈
                cur = cur->left;                // 左
            } 
            else {
                cur = s.top();   s.pop();       // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                res.push_back(cur->val);        // 中
                cur = cur->right;               // 右
            }
        }
        
        return res;
    }
};

（3）后序遍历

跟前序的很像，中序是三个当中差距最大的

class Solution {
public:
    //后续迭代最难，有些结点反复进出栈
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        if (root == nullptr)   return res;

        s.push(root);
        while(!s.empty()){
            auto node = s.top();   s.pop();
            res.push_back(node->val);             //中
            
            //这两步相对于前序  顺序换了
            if(node->left)  s.push(node->left);    //左
            if(node->right) s.push(node->right);   //右  
        }
        reverse(res.begin(), res.end()); // 将结果反转之后就是左右中的顺序了
        
        return res;
    }
};

二叉树的层序遍历

102. 二叉树的层序遍历

通过队列实现

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector <vector <int>> res;
        if (root == nullptr)  return res;    //排除空二叉树情况

        queue <TreeNode*> q;
        q.push(root);    //根结点入队

        while (!q.empty()) {
            int currentLevelSize = q.size();   //记录当前层的结点个数
            res.push_back(vector <int>());

            for (int i = 1; i <= currentLevelSize; ++i) {
                auto node = q.front();             //获取队头元素
                q.pop();                           //删除队头元素
                res.back().push_back(node->val);   //往ret的最后一个容器中压元素
                
                if (node->left)  q.push(node->left);  
                if (node->right) q.push(node->right);
            }
        }

        return res;
    }
};

107. 二叉树的层序遍历 II【中等】

【代码随想录】第8章二叉树_二叉树_09

思路：把层序遍历的结果reverse一下再输出

reverse(res.begin(), res.end());

完整代码不记录

199. 二叉树的右视图【中等】

【代码随想录】第8章二叉树_二叉树_10

思路：层次遍历存储每层最后一个元素

class Solution {
public:
  vector<int> rightSideView(TreeNode* root) {
    vector<int> res;
    if (root == nullptr) return res;

    queue<TreeNode*> q;
    q.push(root);

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

      for (int i = 1; i <= currentSize; ++i) {
        auto node = q.front();
        q.pop();
        if (i == currentSize)  res.push_back(node->val);

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

    return res;
  }
};

637. 二叉树的层平均值【简单】

【代码随想录】第8章二叉树_c++_11

class Solution {
public:
  vector<double> averageOfLevels(TreeNode* root) {
    vector<double> res;
    if (root == nullptr) return res;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
      int currentSize = q.size();
      double num = 0;    //注意是double

      for (int i = 1; i <= currentSize; ++i) {
        auto node = q.front();
        q.pop();
        num += node->val;

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

            res.push_back(num / currentSize);
    }

    return res;
  }
};

429. N 叉树的层序遍历【中等】

【代码随想录】第8章二叉树_递归_12

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

    Node() {}

    Node(int _val) {
        val = _val;
    }

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

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> res;
        if(root == nullptr) return res;

        queue<Node*> q;
        q.push(root);

        while(!q.empty()){
            res.push_back(vector<int> ());
            int currentSize = q.size();

            for(int i = 1; i <= currentSize; ++i){
                auto node = q.front();
                q.pop();
                res.back().push_back(node->val);

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

        return res;
    }
};

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

【代码随想录】第8章二叉树_递归_13

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> res;
        if(root == nullptr) return res;

        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty()){
            int currentSize = q.size();
            int nowMax = INT_MIN;
            for(int i = 1; i <= currentSize; ++i){
                auto node = q.front();
                q.pop();
                nowMax = max(node->val, nowMax);

                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            res.push_back(nowMax);
        }

        return res;
    }
};

116. 填充每个节点的下一个右侧节点指针【中等】

【代码随想录】第8章二叉树_c++_14

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) return root;

        queue<Node*>q;
        q.push(root);
        while (!q.empty()) {
            int current_level_size = q.size();
            for (int i = 1; i <= current_level_size; ++i) {
                auto node = q.front();
                q.pop();

                if (i < current_level_size) node->next = q.front();   //实现next指向
                else node->next = NULL;
                
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);

            }
        }
        
        return root;
    }
};

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

与116题做法一模一样，这里写了代码随想录的解法；116题写的是我自己习惯的解法。

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

        while (!que.empty()) {
            int currentSize = que.size();

            Node* nodePre;
            Node* node;
            for (int i = 1; i <= currentSize; i++) {
                if (i == 0) {
                    nodePre = q.front(); // 取出一层的头结点
                    q.pop();
                    node = nodePre;
                    continue;
                } 

                node = q.front();
                q.pop();
                nodePre->next = node;    // 本层前一个节点next指向本节点
                nodePre = nodePre->next;

                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            
            nodePre->next = NULL;    // 本层最后一个节点指向NULL
        }
        
        return root;
    }
};

104. 二叉树的最大深度【简单】

【代码随想录】第8章二叉树_递归_15

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

        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int currentSize = q.size();
            for(int i = 1; i <= currentSize; ++i){
                auto node = q.front();
                q.pop();

                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            res++;
        }

        return res;
    }
};

111. 二叉树的最小深度【简单】

【代码随想录】第8章二叉树_二叉树_16

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

        queue <TreeNode*> q;
        q.push(root);    //根结点入队

        while (!q.empty()) {
            int currentLevelSize = q.size();   //记录当前层的结点个数
            res++;

            for (int i = 1; i <= currentLevelSize; i++) {  //队列弹出当前层所有元素   并压入下一层所有元素
                auto node = q.front();
                q.pop();

                if (node->left == nullptr && node->right == nullptr) {
                    return res;
                }

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

        return res;
    }
};

3. 翻转二叉树

226. 翻转二叉树【简单】

相同题目：剑指 Offer 27. 二叉树的镜像

【代码随想录】第8章二叉树_二叉树_17

迭代：

广度优先遍历，即层次遍历

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

    while (!q.empty()) {
      auto node = q.front();              
      q.pop();
      
            swap(node->left, node->right);

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

    return root;
  }
};

深度优先遍历就是把queue换成stack

递归：

递归三部曲：

确定递归函数的参数和返回值：TreeNode* invertTree(TreeNode* root)
确定终止条件：if(root == nullptr) return NULL
确定单层递归的逻辑

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr) return NULL;

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

        return root;
    }
};

上面是递归的前序遍历

递归的中序遍历这里是不行的

4. 对称二叉树

101. 对称二叉树【简单】

相同题目：剑指 Offer 28. 对称的二叉树

【代码随想录】第8章二叉树_c++_18

迭代：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr) return true;

        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);

        while(!q.empty()){
            auto leftNode = q.front(); q.pop();
            auto rightNode = q.front(); q.pop();

            if(leftNode == nullptr && rightNode == nullptr) continue;   //少了报错

            if(leftNode == nullptr && rightNode != nullptr) return false;
            if(leftNode != nullptr && rightNode == nullptr) return false;
            if(leftNode->val != rightNode->val) return false;

            q.push(leftNode->left);
            q.push(rightNode->right);
            q.push(leftNode->right);
            q.push(rightNode->left);
        }

        return true;
    }
};

同样的queue改成stack也可以，其他原封不动

递归：

递归三部曲：

确定递归函数的参数和返回值：bool compare(TreeNode* left, TreeNode* right)
确定终止条件
确定单层递归逻辑

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right){  //1.确定递归函数的参数
        //2.确定终止条件
        if(left == nullptr && right == nullptr) return true;
        else if(left == nullptr && right != nullptr) return false;
        else if(left != nullptr && right == nullptr) return false;
        else if(left->val != right->val) return false;
        
        //3.返回值
        return compare(left->left, right->right) && compare(left->right, right->left);
    }

    bool isSymmetric(TreeNode* root) {
        if(root == nullptr) return true;

        return compare(root->left, root->right);
    }
};

100. 相同的树【简单】

【代码随想录】第8章二叉树_递归_19

递归：

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == nullptr && q == nullptr) return true;
        else if(p == nullptr && q != nullptr) return false;
        else if(p != nullptr && q == nullptr) return false;
        else 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) {
        if(p == nullptr && q == nullptr) return true;
        if(p == nullptr || q == nullptr) return false;

        queue<TreeNode*> que;
        que.push(p);
        que.push(q);

        while(!que.empty()){
            auto pNode = que.front(); que.pop();
            auto qNode = que.front(); que.pop();

            if(pNode->val != qNode->val)  return false;


            auto pLeft = pNode->left, pRight = pNode->right, qLeft = qNode->left, qRight = qNode->right;

            if(pLeft == nullptr && qLeft != nullptr) return false;
            else if(pLeft != nullptr && qLeft == nullptr) return false;
            else if(pLeft != nullptr && qLeft != nullptr){
                que.push(pLeft);
                que.push(qLeft);
            }

            if(pRight == nullptr && qRight != nullptr) return false;
            else if(pRight != nullptr && qRight == nullptr) return false;
            else if(pRight != nullptr || qRight != nullptr) {
                que.push(pRight);
                que.push(qRight);
            }

        }

        return true;
    }
};

572. 另一棵树的子树【简单】

【代码随想录】第8章二叉树_递归_20

5. 二叉树的最大深度

104. 二叉树的最大深度【简单】

迭代方法看上面层次遍历，这里讲递归方法

class Solution {
public:
    int maxDepth(TreeNode* root) {
        //2.确定单层终止条件
        if(root == nullptr) return 0;
        
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};

559. N 叉树的最大深度【简单】

迭代：

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

    Node() {}

    Node(int _val) {
        val = _val;
    }

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

class Solution {
public:
    int maxDepth(Node* root) {
        int res = 0;
        if(root == nullptr) return res;
        queue<Node*> q;
        q.push(root);

        while(!q.empty()){
            int currentSize = q.size();
            res++;

            for(int i = 1; i <= currentSize; ++i){
                auto node = q.front();
                q.pop();

                for(auto j : node->children){
                    q.push(j);
                }
            }
        }

        return res;
    }
};

递归：

class Solution {
public:
    int maxDepth(Node* root) {
        int res = 0;
        if(root == nullptr)  return res;
        
        for(auto node : root->children){
            res = max(res, maxDepth(node));
        }

        return res + 1;
    }
};

6. 二叉树的最小深度

111. 二叉树的最小深度【简单】

递归：

class Solution {
public:
    int getDepth(TreeNode* node) {
        if (node == NULL) return 0;
        int leftDepth = getDepth(node->left);           // 左
        int rightDepth = getDepth(node->right);         // 右
                                                        // 中
        // 当一个左子树为空，右不为空，这时并不是最低点
        if (node->left == NULL && node->right != NULL) { 
            return 1 + rightDepth;
        }   
        // 当一个右子树为空，左不为空，这时并不是最低点
        if (node->left != NULL && node->right == NULL) { 
            return 1 + leftDepth;
        }
        
        int result = 1 + min(leftDepth, rightDepth);
        return result;
    }

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

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

222. 完全二叉树的节点个数【中等】

【代码随想录】第8章二叉树_算法_21

迭代：

时间复杂度：O(n)

空间复杂度：O(n)

class Solution {
public:
    int countNodes(TreeNode* root) {
        int res = 0;
        if(root == nullptr) return res;
        queue<TreeNode*> q;
        q.push(root);

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

                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            res += currentSize;
        } 

        return res;
    }
};

递归：

递归三部曲：

确定递归函数的参数和返回值
确定终止条件
确定单层递归逻辑

时间复杂度：O(n)

空间复杂度：O(logn)

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root == nullptr) return 0;
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};

// 版本一
class Solution {
private:
    int getNodesNum(TreeNode* cur) {
        if (cur == 0) return 0;
        int leftNum = getNodesNum(cur->left);      // 左
        int rightNum = getNodesNum(cur->right);    // 右
        int treeNum = leftNum + rightNum + 1;      // 中
        return treeNum;
    }
public:
    int countNodes(TreeNode* root) {
        return getNodesNum(root);
    }
};

8. 平衡二叉树

110. 平衡二叉树【简单】

【代码随想录】第8章二叉树_数据结构_22

高度和深度的区别：

【代码随想录】第8章二叉树_递归_23

迭代：

class Solution {
public:
    //求对应结点的深度，就是它的高度
/*
    int getDepth(TreeNode* cur) {
        int res = 0;
        if (cur == nullptr) return res;
        queue<TreeNode*> q;
        q.push(cur);

        while (!q.empty()) {
            res++;
            int currentSize = q.size();
            for (int i = 1; i <= currentSize; i++) {
                auto node = q.front();
                q.pop();

                if (node->right) q.push(node->right);  // 右
                if (node->left) q.push(node->left);    // 左
            }
        }
        return res;
    }
*/
    int getDepth(TreeNode* root){
        if(root == nullptr) return 0;
        return 1 + max(getDepth(root->left), getDepth(root->right));
    }

    bool isBalanced(TreeNode* root) {
        if (root == nullptr) return true;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            auto node = q.front();                       
            q.pop();

            if (abs(getDepth(node->left) - getDepth(node->right)) > 1) {
                return false;
            }

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

        return true;
    }
};

递归：

时间复杂度：O(n^2)

空间复杂度：O(n)

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

    bool isBalanced(TreeNode* root) {
        if(root == nullptr) return true;

        return abs(getDepth(root->left) - getDepth(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
};

时间复杂度：O(n)

空间复杂度：O(n)

class Solution {
public:
    // 返回以该节点为根节点的二叉树的高度，如果不是二叉搜索树了则返回-1
    int getHeight(TreeNode* node) {
        if (node == nullptr)  return 0;

        int leftHeight = getHeight(node->left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(node->right);
        if (rightHeight == -1) return -1;
        
        return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
    }

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

9. 二叉树的所有路径

257. 二叉树的所有路径【简单】

【代码随想录】第8章二叉树_递归_24

迭代：

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

        queue<TreeNode*> q;
        q.push(root);
        queue<string> p;
        p.push(to_string(root->val));

        while(!q.empty()){
            auto node = q.front();
            q.pop();
            string path = p.front();
            p.pop();

            if(node->left == nullptr && node->right == nullptr){ //遇到叶子结点
                res.push_back(path);
            }

            if(node->left){
                q.push(node->left);
                p.push(path + "->" + to_string(node->left->val));
            }
            if(node->right){
                q.push(node->right);
                p.push(path + "->" + to_string(node->right->val));
            }
        }

        return res;
    }
};

递归：

class Solution {
public:
  void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {  //1.确定递归函数的参数和返回值
    path.push_back(cur->val);
    
    // 这才到了叶子节点
    if (cur->left == NULL && cur->right == NULL) {   //2.确定终止条件
      string sPath;
      for (int i = 0; i < path.size(); i++) {
        sPath += to_string(path[i]);
        if(i != path.size() - 1)  sPath += "->";
      }
      result.push_back(sPath);
      return;
    }

        //3.确定单层递归逻辑
    if (cur->left) {
      traversal(cur->left, path, result);  //回溯和递归是一一对应的，有一个递归，就要有一个回溯
      path.pop_back(); // 回溯
    }
    if (cur->right) {
      traversal(cur->right, path, result);
      path.pop_back(); // 回溯
    }
  }

  vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> result;
    vector<int> path;

    if (root == NULL) return result;
    
    traversal(root, path, result);
    
    return result;
  }
};

精简版：

class Solution {
public:
    void traversal(TreeNode* cur, string path, vector<string>& result) { //回溯体现在string不是引用类型
        path += to_string(cur->val); // 中
        if (cur->left == NULL && cur->right == NULL) {
            result.push_back(path);
            return;
        }
        
        if (cur->left)   traversal(cur->left, path + "->", result); // 左
        if (cur->right)  traversal(cur->right, path + "->", result); // 右
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;
    }
};

10. 左叶子之和

404. 左叶子之和【简单】

【代码随想录】第8章二叉树_c++_25

迭代：

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        int res = 0;
        if(root == nullptr) return res;
        queue<TreeNode*> q;
        q.push(root);

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

                if(node->left) {
                    if(node->left->left == nullptr && node->left->right == nullptr){
                        res += node->left->val;
                    }
                    else{
                        q.push(node->left);
                    }
                }
                if(node->right) q.push(node->right);
            }
        }

        return res;
    }
};

递归：

时间复杂度：O(n)

空间复杂度：O(n)

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

        int leftValue = sumOfLeftLeaves(root->left);
        int rightValue = sumOfLeftLeaves(root->right); 
        
        int midValue = 0;
        if(root->left && root->left->left == nullptr && root->left->right == nullptr){
            midValue = root->left->val;
        }

        return midValue + leftValue + rightValue;
    }
};

11. 找树左下角的值

513. 找树左下角的值【简单】

【代码随想录】第8章二叉树_递归_26

迭代：

层序遍历修改返回值即可

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        vector<vector<int>> v;
        if(root == nullptr) return 0;
        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty()){
            int currentSize = q.size();
            v.push_back(vector<int> ());

            for(int i = 1; i <= currentSize; ++i){
                auto node = q.front();
                q.pop();

                v.back().push_back(node->val);

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

        return v.back()[0];
    }
};

空间优化：用一个常量空间记录每一层的第一个数

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        //vector<vector<int>> v;
        if(root == nullptr) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int res = 0;

        while(!q.empty()){
            int currentSize = q.size();
            //v.push_back(vector<int> ());
            res = q.front()->val;   //记录每一层的第一个元素

            for(int i = 1; i <= currentSize; ++i){
                auto node = q.front();
                q.pop();

                //v.back().push_back(node->val);

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

        return res;
    }
};

12. 路径总和

112. 路径总和【简单】

【代码随想录】第8章二叉树_算法_27

迭代：

时间复杂度：O(n)

空间复杂度：O(n)

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        queue<pair<TreeNode*, int>> q;
        q.push(make_pair(root, root->val));

        while (!q.empty()) {
            pair<TreeNode*, int> node = q.front();
            q.pop();  //两个容器   删除的差距

            if (!node.first->left && !node.first->right && node.second == targetSum) return true;

            if (node.first->left) q.push(make_pair(node.first->left, node.second + node.first->left->val));
            if (node.first->right) q.push(make_pair(node.first->right, node.second + node.first->right->val));
        }

        return false;
    }
};

递归：

时间复杂度：O(n)

空间复杂度：O(h)，h为树的高度

空间复杂度主要取决于递归时栈空间的开销

class Solution {
public:
    bool hasPathSum(TreeNode *root, int targetSum) {   //1.确定递归函数的参数和返回值
        if (root == nullptr)   return false;     //2.确定终止条件
        
        if (root->left == nullptr && root->right == nullptr) {   //3.确定单层递归逻辑
            return targetSum == root->val;
        }
        
        return hasPathSum(root->left, targetSum - root->val) ||
               hasPathSum(root->right, targetSum - root->val);
    }
};

113. 路径总和 II【中等】

【代码随想录】第8章二叉树_递归_28

迭代：

时间复杂度：O(n^2)

空间复杂度：O(n)；主要取决于哈希表和队列空间的开销

n是树的节点数

class Solution {
public:
    vector<vector<int>> res;
    unordered_map<TreeNode*, TreeNode*> parent;  //第二参数为该节点的父结点
    
    void getPath(TreeNode* node){  //一路往父节点回溯，合成一个vector路径
        vector<int> temp;
        while(node != nullptr){
            temp.push_back(node->val);
            node = parent[node];
        }
        reverse(temp.begin(), temp.end());  //因为是反的
        res.push_back(temp);                    //添加到res里面
    }
    
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(root == nullptr)  return res;  //排除空树情况

        queue<TreeNode*> q;
        q.push(root);
        queue<int> qValue;
        qValue.push(root->val);

        while(!q.empty()){
            auto node = q.front();
            q.pop();
            int value = qValue.front();
            qValue.pop();
            
            //到叶子结点  且刚好==target
            if(node->left == nullptr && node->right == nullptr && value == targetSum)   getPath(node);   
            
            if(node->left){
                parent[node->left] = node;
                q.push(node->left);
                qValue.push(value + node->left->val);
            }     
            
            if(node->right){
                parent[node->right] = node;
                q.push(node->right);
                qValue.push(value + node->right->val);
            }
        }
        
        return res;
    }
};

递归：

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

class Solution{
public:
    vector<vector<int>> res;
    vector<int> path;
    
    void traversal(TreeNode* node, int count){
        //找到目标
        if(node->left == nullptr && node->right == nullptr && count == 0){
            res.push_back(path);
            return;
        }   
        
        if(node->left == nullptr && node->right == nullptr)  return;
        
        if(node->left){
            path.push_back(node->left->val);
            count -= node->left->val;
            traversal(node->left, count);
            count += node->left->val;  //回溯
            path.pop_back();           //回溯
        }
        
        if(node->right){
            path.push_back(node->right->val);
            count -= node->right->val;
            traversal(node->right, count);
            count += node->right->val;  //回溯
            path.pop_back();            //回溯
        }
        
        return;
    }
    
    
    vector<vector<int>> pathSum(TreeNode* root, int sum){
        if(root == nullptr) return res;
        
        path.push_back(root->val);  //把根结点放入路径
        
        traversal(root, sum - root->val);
        
        return res;
    }
};

13. 构造一棵二叉树

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

【代码随想录】第8章二叉树_二叉树_29

递归

先切中序遍历的数组，分成左右两个数组
再切后序遍历的数组，分成左右两个数组
递归左数组和右数组

class Solution {
public:
    TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size() == 0) return NULL;  //in和pos的size都一样，随意

        // 后序遍历数组最后一个元素，就是当前的中间节点
        int rootValue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootValue);

        // 叶子节点
        if (postorder.size() == 1) return root;

        // 找到中序遍历的切割点
        int delimiterIndex;
        for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }

        // 切割中序数组
        // 左闭右开区间：[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 = traversal(leftInorder, leftPostorder);
        root->right = traversal(rightInorder, rightPostorder);

        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0)  return NULL;
        return traversal(inorder, postorder);
    }
};

优化：数组空间优化

用几个常数索引优化数组

class Solution {
public:
    // 中序区间：[inorderBegin, inorderEnd)，后序区间[postorderBegin, postorderEnd)
    TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {
        if (postorderBegin == postorderEnd) return NULL;

        // 后序遍历数组最后一个元素，就是当前的中间节点
        int rootValue = postorder[postorderEnd - 1];
        TreeNode* root = new TreeNode(rootValue);

         // 叶子节点
        if (postorderEnd - postorderBegin == 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;

        // 切割后序数组
        // 左后序区间，左闭右开[leftPostorderBegin, leftPostorderEnd)
        int leftPostorderBegin =  postorderBegin;
        int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
        // 右后序区间，左闭右开[rightPostorderBegin, rightPostorderEnd)
        int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);
        int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素，已经作为节点了

        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  postorder, leftPostorderBegin, leftPostorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);

        return root;
    }
    
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0) return NULL;
        // 左闭右开的原则
        return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
};

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

【代码随想录】第8章二叉树_二叉树_30

与上题一个思路

先切中序遍历的数组，分成左右两个数组
再切前序遍历的数组，分成左右两个数组
递归左数组和右数组

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

        //前序遍历的第一个元素就是当前中间结点
        int rootValue = preorder[0];
        TreeNode* root = new TreeNode(rootValue);

        //叶子结点
        if(preorder.size() == 1) return root;

        //找到中序遍历的切割点
        int delimiterIndex;
        for(delimiterIndex = 0; delimiterIndex < inorder.size(); ++delimiterIndex){
            if(inorder[delimiterIndex] == rootValue)  break;
        }

        //切割中序数组
        //左闭右开区间： [0, delimiterInedx)
        vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
        //[delimiterIndex + 1, end)
        vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end());

        //切割前序数组
        //[1, leftInorder.size)
        vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + 1 + leftInorder.size());
        //[leftInorder.size, end)
        vector<int> rightPreorder(preorder.begin() + 1 + leftInorder.size(), preorder.end());

        root->left = traversal(leftPreorder, leftInorder);
        root->right = traversal(rightPreorder, rightInorder);

        return root;
    }

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

14. 最大二叉树

654. 最大二叉树【中等】

【代码随想录】第8章二叉树_二叉树_31

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* node = new TreeNode(0);
        if (nums.size() == 1) {      //3. 确定终止条件
            node->val = nums[0];
            return node;
        }
        
        // 1. 找到数组中最大的值和对应的下标
        int maxValue = 0;
        int maxValueIndex = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
                maxValueIndex = i;
            }
        }
        node->val = maxValue;   //2. 确定中间结点
        
        // 最大值所在的下标左区间 构造左子树
        if (maxValueIndex > 0) {
            vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
            node->left = constructMaximumBinaryTree(newVec);
        }
        
        // 最大值所在的下标右区间 构造右子树
        if (maxValueIndex < (nums.size() - 1)) {
            vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
            node->right = constructMaximumBinaryTree(newVec);
        }
        
        return node;
    }
};

数组空间优化：

class Solution {
public:
    // 在左闭右开区间[left, right)，构造二叉树
    TreeNode* traversal(vector<int>& nums, int left, int right) {
        if (left >= right) return nullptr;

        // 分割点下标：maxValueIndex
        int maxValueIndex = left;
        for (int i = left + 1; i < right; ++i) {
            if (nums[i] > nums[maxValueIndex])  maxValueIndex = i;
        }

        TreeNode* root = new TreeNode(nums[maxValueIndex]);

        // 左闭右开：[left, maxValueIndex)
        root->left = traversal(nums, left, maxValueIndex);
        // 左闭右开：[maxValueIndex + 1, right)
        root->right = traversal(nums, maxValueIndex + 1, right);

        return root;
    }

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return traversal(nums, 0, nums.size());
    }
};

15. 合并二叉树

617. 合并二叉树【简单】

【代码随想录】第8章二叉树_算法_32

迭代：把第二棵树合在第一棵树上，返回第一棵树

class Solution {
public:
  TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    if (root1 == nullptr) return root2;   //排除两种极端情况
    if (root2 == nullptr) return root1;

    queue<TreeNode*> q;  
        q.push(root1);  
        q.push(root2);

    while (!q.empty()) {
      auto node1 = q.front();  q.pop();
      auto node2 = q.front();  q.pop();
      node1->val += node2->val;
       
      if (node1->left && node2->left) {
        q.push(node1->left);
        q.push(node2->left);
      }
      else if (node2->left)   node1->left = node2->left;  //树1左子树没有了  把树2左子树合到树1上

      if (node1->right && node2->right) {
        q.push(node1->right);
        q.push(node2->right);
      }
      else if (node2->right)   node1->right = node2->right;  //树1右子树没有了  把树2右子树合到树1上
    }
        
    return root1;
  }
};

递归：

class Solution {
public:
  TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {   //1.确定递归的参数和返回值
    if (t1 == nullptr)  return t2;                   //2.确定终止条件
    if (t2 == nullptr)  return t1;

    //下面三句代码的顺序可以颠倒                       3.确定单层递归逻辑
    auto root = new TreeNode(t1->val + t2->val);
    root->left = mergeTrees(t1->left, t2->left);
    root->right = mergeTrees(t1->right, t2->right);

    return root;
  }
};

16. 二叉搜索树

做二叉搜索树的题就是跟中序遍历有关，中序遍历的递归和迭代方法

700. 二叉搜索树中的搜索【简单】

【代码随想录】第8章二叉树_递归_33

思路一：层序遍历上修改，即迭代法

class Solution {
public:
  TreeNode* searchBST(TreeNode* root, int val) {
    if (root == nullptr) return NULL;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
      TreeNode* node = q.front();
      q.pop();
      if (node->val == val) {
        return node;
      }
      else {
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
      }
    }

    return NULL;
  }
};

改进：加上二叉搜索数的特点修改

//二叉搜索树是一个有序数   左<中<右
class Solution {
public:
  TreeNode* searchBST(TreeNode* root, int val) {
        auto node = root;
    while (node != nullptr) {
            if(node->val == val)  return node;
      else if (node->val > val)  node = node->left;    //结点值>目标值  在左子树
      else if (node->val < val)  node = node->right;   //结点值<目标值  在右子树
    }

    return NULL;     //未搜索到，返回
  }
};

递归：

class Solution {
public:
  TreeNode* searchBST(TreeNode* root, int val) {   //1.确定递归函数参数和返回值
    if (root == nullptr) return NULL; 
    if (root->val == val) return root;   //2.确定终止条件
    else if (root->val > val) return searchBST(root->left, val);   //3.确定单层递归逻辑
    else if (root->val < val) return searchBST(root->right, val);

    return NULL;
  }
};

98. 验证二叉搜索树【中等】

【代码随想录】第8章二叉树_算法_34

思路：二叉搜索树的中序遍历是一个有序数组

class Solution {
public:
    void inorder(TreeNode* root, vector<int>& res) {
        if (!root) return;

        inorder(root->left, res);   //左
        res.push_back(root->val);   //中
        inorder(root->right, res);  //右
    }

    bool isValidBST(TreeNode* root) {
        vector<int> res;
        inorder(root, res);

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

迭代法：模拟中序遍历的迭代

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = NULL; // 记录前一个节点

        while (cur != NULL || !st.empty()) {
            if (cur != NULL) {
                st.push(cur);
                cur = cur->left;                // 左
            }
            else {
                cur = st.top();                 // 中
                st.pop();

                if (pre != NULL && cur->val <= pre->val)   //多了这句
                    return false;
                pre = cur;                                 //保存前一个访问的结点

                cur = cur->right;               // 右
            }
        }
        return true;
    }
};

530. 二叉搜索树的最小绝对差【简单】

【代码随想录】第8章二叉树_数据结构_35

与上一题很类似，中序遍历成数组，然后遍历数组找到minDistinct

class Solution {
public:
    void inorder(TreeNode* root, vector<int>& res) {
        if (!root) return;

        inorder(root->left, res);   //左
        res.push_back(root->val);   //中
        inorder(root->right, res);  //右
    }

    int getMinimumDifference(TreeNode* root) {
        vector<int> res;
        inorder(root, res);
        int minDistinct = INT_MAX;
        for(int i = 1; i < res.size(); ++i){
            minDistinct = min(minDistinct, res[i] - res[i-1]);
        }
        return minDistinct;
    }
};

优化：

class Solution {
public:
    int result = INT_MAX;
    TreeNode* pre;   //记录前一个
    
    void traversal(TreeNode* cur) {   //1.确定递归函数参数和返回值
        if (cur == nullptr) return;   //2.确定终止条件
        
        //3.确定单层递归逻辑
        traversal(cur->left);   // 左
        if (pre != nullptr){       // 中
            result = min(result, cur->val - pre->val);
        }
        pre = cur; // 记录前一个
        traversal(cur->right);  // 右
    }

    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        return result;
    }
};

迭代：

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        int minDistinct = INT_MAX;
        
        while (cur != nullptr || !s.empty()) {
            if (cur != nullptr) {                  // 指针来访问节点，访问到最底层
                s.push(cur);                    // 将访问的节点放进栈
                cur = cur->left;                // 左
            } 
            else {
                cur = s.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                s.pop();
                res.push_back(cur->val);        // 中
                
                if (pre != NULL)  minDistinct = min(minDistinct, cur->val - pre->val);   //多了这句
                pre = cur;                                 //保存前一个访问的结点
                
                cur = cur->right;               // 右
            }
        }
        
        return minDistinct;
    }
};

501. 二叉搜索树中的众数【简单】

【代码随想录】第8章二叉树_递归_36

题目意思：所有众数，不是一个

递归：

class Solution {
private:
    void searchBST(TreeNode* cur, unordered_map<int, int>& map) { // 前序遍历
        if (cur == NULL) return ;
        map[cur->val]++; // 统计元素频率
        searchBST(cur->left, map);
        searchBST(cur->right, map);
        return ;
    }
    
    bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {
        return a.second > b.second;
    }
    
public:
    vector<int> findMode(TreeNode* root) {
        unordered_map<int, int> map; // key:元素，value:出现频率
        vector<int> result;
        if (root == nullptr) return result;
        
        searchBST(root, map);                                // 1.遍历树，统计每个元素的次数
        
        vector<pair<int, int>> vec(map.begin(), map.end());  // 2.map赋值给vector
        sort(vec.begin(), vec.end(), cmp);                   // 3.给频率排个序
        
        result.push_back(vec[0].first);
        for (int i = 1; i < vec.size(); i++) {               // 4.众数可能不止一个
            // 取最高的放到result数组中
            if (vec[i].second == vec[0].second)  result.push_back(vec[i].first);
            else break;
        }
        
        return result;
    }
};

以上是任何树都可以用的方法，没用到二叉搜索树的性质

回顾中序遍历的递归版本：

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

    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        preorder(root, res);
        return res;
    }
};

利用了二叉搜索树特点的递归方法：

class Solution {
private:
    int maxCount; // 最大频率
    int count; // 统计频率
    TreeNode* pre;
    vector<int> result;
    
    void searchBST(TreeNode* cur) {
        if (cur == nullptr)  return;

        searchBST(cur->left);       // 左
                                    // 中
        if (pre == NULL)  count = 1;             // 第一个节点
        else if (pre->val == cur->val) count++;  // 与前一个节点数值相同
        else    count = 1;                       // 与前一个节点数值不同
        
        pre = cur; // 更新上一个节点

        if (count == maxCount) { // 如果和最大值相同，放进result中
            result.push_back(cur->val);
        }
        else if (count > maxCount) { // 如果计数大于最大值频率
            maxCount = count;   // 更新最大频率
            result.clear();     // 很关键的一步，不要忘记清空result，之前result里的元素都失效了
            result.push_back(cur->val);
        }

        searchBST(cur->right);      // 右
        return;
    }

public:
    vector<int> findMode(TreeNode* root) {
        //初始化所有参数
        count = 0;
        maxCount = 0;
        TreeNode* pre = NULL; // 记录前一个节点
        result.clear();

        searchBST(root);
        return result;
    }
};

回顾一下迭代版本中序遍历：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* cur = root;
        
        while (cur != nullptr || !s.empty()) {
            if (cur != nullptr) {                  // 指针来访问节点，访问到最底层
                s.push(cur);                    // 将访问的节点放进栈
                cur = cur->left;                // 左
            } 
            else {
                cur = s.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                s.pop();
                
                res.push_back(cur->val);        // 中
                
                cur = cur->right;               // 右
            }
        }
        
        return res;
    }
};

迭代：

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        int maxCount = 0;   // 最大频率
        int count = 0;      // 统计频率
        vector<int> res;
        
        while (cur != nullptr || !st.empty()) {
            if (cur != nullptr) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top();
                st.pop();                       // 中
                
                //处理的方法和上面一模一样
                if (pre == nullptr)   count = 1;          // 第一个节点
                else if (pre->val == cur->val)   count++; // 与前一个节点数值相同
                else   count = 1;                         // 与前一个节点数值不同
                
                if (count == maxCount) {    // 如果和最大值相同，放进res中
                    res.push_back(cur->val);
                }
                else if (count > maxCount) { // 如果计数大于最大值频率
                    maxCount = count;   // 更新最大频率
                    res.clear();        // 很关键的一步，不要忘记清空res，之前res里的元素都失效了
                    res.push_back(cur->val);
                }
                pre = cur;
                
                cur = cur->right;               // 右
            }
        }
        
        return res;
    }
};

236. 二叉树的最近公共祖先【中等】

【代码随想录】第8章二叉树_c++_37

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {  //1.
        if (root == q || root == p || root == nullptr) return root;    //2.确定终止条件
        
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        
        if (left != NULL && right != NULL)      return root;
        else if (left == NULL && right != NULL) return right;
        else if (left != NULL && right == NULL) return left;
        else  return NULL; //  (left == NULL && right == NULL)
    }
};

235. 二叉搜索树的最近公共祖先【简单】

思路一：递归

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

思路二：迭代

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int min_val = min(q->val, p->val);
        int max_val = max(q->val, p->val);
        while (root) {
            if (root->val > max_val)      root = root->left;
            else if (root->val < min_val) root = root->right;
            else                          return root;
        }

        return NULL;
    }
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root) {
            if (root->val > p->val && root->val > q->val)   root = root->left;
            else if (root->val < p->val && root->val < q->val) root = root->right;
            else return root;
        }
        return NULL;
    }
};

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

【代码随想录】第8章二叉树_二叉树_38

题目意思：对二叉搜索树进行插入操作，使得插入后的树还为二叉搜索树

思路：采用插入叶子结点的方法

递归：

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == NULL)   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;
    }
};

迭代：

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == nullptr)    return new TreeNode(val);         //空树

        TreeNode* pos = root;
        while (pos != nullptr) {
            if (val < pos->val) {   //val<当前结点  往左走
                if (pos->left == nullptr) {
                    pos->left = new TreeNode(val);
                    break;
                }
                pos = pos->left;
            }
            else {    //往右走
                if (pos->right == nullptr) {
                    pos->right = new TreeNode(val);
                    break;
                }
                pos = pos->right;
            }
        }

        return root;
    }
};

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

【代码随想录】第8章二叉树_数据结构_39

题目意思：删除二叉搜索树中的一个结点，保证删除后的树还是二叉搜索树

【代码随想录】第8章二叉树_数据结构_40

递归：

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
        
        if (root->val == key) {
            // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
            if (root->left == nullptr && root->right == nullptr) {
                ///! 内存释放
                delete root;
                return nullptr;
            }
            // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
            else if (root->left == nullptr) {
                auto retNode = root->right;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
            else if (root->right == nullptr) {
                auto retNode = root->left;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置  并返回删除节点右孩子为新的根节点.
            else {
                TreeNode* cur = root->right; // 找右子树最左面的节点
                while(cur->left != nullptr) {
                    cur = cur->left;
                }
                cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置
                TreeNode* tmp = root;   // 把root节点保存一下，下面来删除
                root = root->right;     // 返回旧root的右孩子作为新root
                delete tmp;             // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）
                return root;
            }
        }
        
        if (root->val > key) root->left = deleteNode(root->left, key);
        if (root->val < key) root->right = deleteNode(root->right, key);
        
        return root;
    }
};

迭代：

class Solution {
public:
    TreeNode* deleteOneNode(TreeNode* target){  //返回删除后的树的头结点
        if(target->right == nullptr && target->left == nullptr)  return nullptr;
        else if(target->right == nullptr && target->left != nullptr)  return target->left;
        else if(target->right != nullptr && target->left == nullptr)  return target->right;
        else{
            TreeNode* cur = target->right;
            while(cur->left != nullptr){
                cur = cur->left;
            }
            cur->left = target->left;
            return target->right;
        }
    }

    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root == nullptr)  return  root;

        TreeNode* cur = root;
        TreeNode* pre = nullptr; //记录待删除结点的父亲结点
        while(cur != nullptr){
            if(key > cur->val){
                pre = cur;
                cur = cur->right;  //增大cur的值
            }       
            else if(key < cur->val){
                pre =  cur;
                cur = cur->left;   //缩小cur的值
            }  
            else if(key == cur->val){  //找到待删除的结点，作相应的删除操作
                if(pre && pre->left == cur){  //删除的是左孩子
                    pre->left = deleteOneNode(cur); 
                    return root;
                }
                else if(pre && pre->right == cur){  //删除的是右孩子
                    pre->right = deleteOneNode(cur);
                    return root;
                }
                else if(pre == nullptr){  //待删除节点刚好是根结点
                    return deleteOneNode(cur);
                }
            }
        }

        return root;  //未搜索到，返回原树
    }
};

669. 修剪二叉搜索树【中等】

【代码随想录】第8章二叉树_递归_41

【代码随想录】第8章二叉树_二叉树_42

递归：

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == nullptr)  return nullptr;
        else if (root->val < low)  return trimBST(root->right, low, high);
        else 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;
    }
};

迭代：

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int L, int R) {
        if (root == nullptr)   return nullptr;   //排除空树情况

        // 处理头结点，让root移动到[L, R] 范围内，注意是左闭右闭
        while (root != nullptr && (root->val < L || root->val > R)) {
            if (root->val < L)  root = root->right; // 小于L往右走
            else                root = root->left; // 大于R往左走
        }
        
        TreeNode *cur = root;
        // 此时root已经在[L, R] 范围内，处理左孩子元素小于L的情况
        while (cur != nullptr) {
            while (cur->left && cur->left->val < L) {
                cur->left = cur->left->right;
            }
            cur = cur->left;
        }
        
        cur = root;
        // 此时root已经在[L, R] 范围内，处理右孩子大于R的情况
        while (cur != nullptr) {
            while (cur->right && cur->right->val > R) {
                cur->right = cur->right->left;
            }
            cur = cur->right;
        }
            
        return root;
    }
};

108. 将有序数组转换为二叉搜索树【简单】

【代码随想录】第8章二叉树_数据结构_43

题目意思：有序数组->平衡二叉搜索树。答案不唯一

递归：

class Solution {
public:
    TreeNode* traversal(vector<int>& nums, int left, int right) {  //1.确定递归函数参数和返回值
        if (left > right)   return nullptr;    //2.确定终止条件
           
        int mid = left + ((right - left) / 2);
        TreeNode* root = new TreeNode(nums[mid]);     //确定根结点
        root->left = traversal(nums, left, mid - 1);  //递归确定左子树
        root->right = traversal(nums, mid + 1, right);//递归确定右子树
        
        return root;
    }

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

迭代：

迭代法可以通过三个队列来模拟，一个队列放遍历的节点，一个队列放左区间下标，一个队列放右区间下标。

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

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

        while (!nodeQue.empty()) {
            auto curNode = nodeQue.front(); nodeQue.pop();
            int left = leftQue.front(); leftQue.pop();
            int right = rightQue.front(); rightQue.pop();
            
            int mid = left + ((right - left) / 2);
            curNode->val = nums[mid];       // 将mid对应的元素给中间节点

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

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

538. 把二叉搜索树转换为累加树【中等】

【代码随想录】第8章二叉树_数据结构_44

【代码随想录】第8章二叉树_c++_45

思路：反中序遍历

递归：

class Solution {
private:
    int pre;
    void traversal(TreeNode* cur) {
        if(cur == nullptr)  return;

        traversal(cur->right); //右
        cur->val += pre;                 //中
        pre = cur->val;
        traversal(cur->left); //左
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        pre = 0;
        traversal(root);
        return root;
    }
};

回顾中序遍历：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* cur = root;
        
        while (cur != nullptr || !s.empty()) {
            if (cur != nullptr) {                  // 指针来访问节点，访问到最底层
                s.push(cur);                    // 将访问的节点放进栈
                cur = cur->left;                // 左
            } 
            else {
                cur = s.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                s.pop();
                res.push_back(cur->val);        // 中
                cur = cur->right;               // 右
            }
        }
        
        return res;
    }
};

**迭代：**就是中序遍历模板题

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

标签：node,right,return,代码,随想录,二叉树,TreeNode,root,left
From： https://blog.51cto.com/u_15902866/5920914

【代码随想录】第8章 二叉树

第8章 二叉树

1. 二叉树理论基础

二叉树种类

（1）满二叉树

（2）完全二叉树

（3）二叉搜索树

（4）平衡二叉搜索树

二叉树的存储方式

二叉树的遍历

二叉树的定义

2. 二叉树的遍历

二叉树的递归遍历

二叉树的迭代遍历

（1）前序遍历

（2）中序遍历

（3）后序遍历

二叉树的层序遍历

​​107. 二叉树的层序遍历 II​​【中等】

​​199. 二叉树的右视图​​【中等】

​​637. 二叉树的层平均值​​【简单】

​​429. N 叉树的层序遍历​​【中等】

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

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

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

​​104. 二叉树的最大深度​​【简单】

​​111. 二叉树的最小深度​​【简单】

3. 翻转二叉树

​​226. 翻转二叉树​​【简单】

4. 对称二叉树

​​101. 对称二叉树​​【简单】

​​100. 相同的树​​【简单】

​​572. 另一棵树的子树​​【简单】

5. 二叉树的最大深度

​​104. 二叉树的最大深度​​【简单】

​​559. N 叉树的最大深度​​【简单】

6. 二叉树的最小深度

​​111. 二叉树的最小深度​​【简单】

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

​​222. 完全二叉树的节点个数​​【中等】

8. 平衡二叉树

​​110. 平衡二叉树​​【简单】

9. 二叉树的所有路径

​​257. 二叉树的所有路径​​【简单】

10. 左叶子之和

​​404. 左叶子之和​​【简单】

11. 找树左下角的值

​​513. 找树左下角的值​​【简单】

12. 路径总和

​​112. 路径总和​​【简单】

​​113. 路径总和 II​​【中等】

13. 构造一棵二叉树

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

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

14. 最大二叉树

​​654. 最大二叉树​​【中等】

15. 合并二叉树

​​617. 合并二叉树​​【简单】

16. 二叉搜索树

​​700. 二叉搜索树中的搜索​​【简单】

​​98. 验证二叉搜索树​​【中等】

​​530. 二叉搜索树的最小绝对差​​【简单】

​​501. 二叉搜索树中的众数​​【简单】

​​236. 二叉树的最近公共祖先​​【中等】

​​235. 二叉搜索树的最近公共祖先​​【简单】

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

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

​​669. 修剪二叉搜索树​​【中等】

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

​​538. 把二叉搜索树转换为累加树​​【中等】

相关文章

赞助商

阅读排行

【代码随想录】第8章二叉树

第8章二叉树

107. 二叉树的层序遍历 II【中等】

199. 二叉树的右视图【中等】

637. 二叉树的层平均值【简单】

429. N 叉树的层序遍历【中等】

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

116. 填充每个节点的下一个右侧节点指针【中等】

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

104. 二叉树的最大深度【简单】

111. 二叉树的最小深度【简单】

226. 翻转二叉树【简单】

101. 对称二叉树【简单】

100. 相同的树【简单】

572. 另一棵树的子树【简单】

104. 二叉树的最大深度【简单】

559. N 叉树的最大深度【简单】

111. 二叉树的最小深度【简单】

222. 完全二叉树的节点个数【中等】

110. 平衡二叉树【简单】

257. 二叉树的所有路径【简单】

404. 左叶子之和【简单】

513. 找树左下角的值【简单】

112. 路径总和【简单】

113. 路径总和 II【中等】

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

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

654. 最大二叉树【中等】

617. 合并二叉树【简单】

700. 二叉搜索树中的搜索【简单】

98. 验证二叉搜索树【中等】

530. 二叉搜索树的最小绝对差【简单】

501. 二叉搜索树中的众数【简单】

236. 二叉树的最近公共祖先【中等】

235. 二叉搜索树的最近公共祖先【简单】

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

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

669. 修剪二叉搜索树【中等】

108. 将有序数组转换为二叉搜索树【简单】

538. 把二叉搜索树转换为累加树【中等】