二叉树系列汇总，持续更新！

╰半橙微兮° 2023-01-16 11:24 141阅读 0赞

### 文章目录 ###

*   *  一、构造二叉树
     *  二、递增顺序搜索树
     *   *  题目
         *  解题
     *  三、二叉搜索树范围和（LeetCode 938）
     *   *  题目
         *  题解
     *  四、二叉搜索树的第k大节点
     *   *  题目
         *  题解
     *  五、二叉树的深度
     *   *  题目
         *  解析
     *  六、员工的重要性
     *   *  题目
         *  题解
     *  七、平衡二叉树
     *   *  题目
         *  题解
     *  八、对称二叉树
     *   *  题目
         *  题解
     *  九、二叉树的镜像
     *   *  题目
         *  题解

**相关文章汇总：**

*  [动态规划系列汇总，持续更新！][Link 1]
 *  [最小路径和问题汇总，持续更新！][Link 2]
 *  [跳跃游戏系列汇总，持续更新！][Link 3]

--------------------

## 一、构造二叉树 ##

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

--------------------

## 二、递增顺序搜索树 ##

### 题目 ###

给你一棵二叉搜索树，请你按中序遍历将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，
    并且每个节点没有左子节点，只有一个右子节点。

![\*\*示例 1：\*\*][1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]

### 解题 ###

class Solution { 
    public:
    
        //将二叉搜索树转换为一个排序好的vector
        void orderTree2vector(TreeNode *node, vector<int> &vec)
        { 
            if(node==nullptr) return;
    
            orderTree2vector(node->left, vec);
            vec.push_back(node->val);
            orderTree2vector(node->right, vec);
        }
    
        //将二叉搜索树转换成递增顺序搜索树
        TreeNode* increasingBST(TreeNode* root) { 
            vector <int>vec;
            orderTree2vector(root, vec);
            //创建一个新的节点
            TreeNode *newNode = new TreeNode(-1);
            TreeNode *currNode = newNode;
    
            for(int value: vec)
            { 
                currNode->right = new TreeNode(value);
                currNode = currNode->right;
            }
            return newNode->right;
        }
    };

**复杂度分析：**

*  时间复杂度：O(n)，其中 n 是二叉搜索树的节点总数。
 *  空间复杂度：O(n)，其中 n 是二叉搜索树的节点总数。需要长度为 n 的列表保存二叉搜索树的所有节点的值。

**提交结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 1]

--------------------

## 三、二叉搜索树范围和（LeetCode 938） ##

### 题目 ###

给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
    
    提示：
    树中节点数目在范围 [1, 2 * 104] 内
    1 <= Node.val <= 105
    1 <= low <= high <= 105
    所有 Node.val 互不相同
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/range-sum-of-bst
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 3]

### 题解 ###

本题可以通过中序遍历将二叉树中的值按顺序存储到一个数组中，然后再计算\[low, high\]之间的数的和，但是并不推荐这么做。我们可以利用二叉搜索树本身的结构，以及有序性的性质 ，利用更小的复杂度来解决本题。

**解法：深度优先搜索**

按深度优先搜索的顺序计算范围和。记当前子树根节点为 root，分以下四种情况讨论：

*  root 节点为空，说明已经搜索到叶子节点（没有子节点），返回0。
 *  root 节点的值 root->value > high，则无需考虑右子树，返回左子树的范围和。
 *  root 节点的值 root->value < low，则无需考虑左子树，返回右子树的范围和。
 *  root 节点的值 low< root->value < high 此时应返回 root 节点的值、左子树的范围和、右子树的范围和这三者之和。

C++实现如下：

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

**复杂度分析：**

*  时间复杂度：O(n)，其中 nn 是二叉搜索树的节点数。
 *  空间复杂度：O(n)。空间复杂度主要取决于栈空间的开销。

--------------------

## 四、二叉搜索树的第k大节点 ##

### 题目 ###

给定一棵二叉搜索树，请找出其中第k大的节点。
    
    限制：
    1 ≤ k ≤ 二叉搜索树元素个数
    
    原题：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 4]

### 题解 ###

class Solution { 
    public:
    	// 倒序遍历二插入，将数字从大到小存入数组vec中
        void orderTree2vector(TreeNode* root, vector<int> &vec)
        { 
            if(root==nullptr) return;
            orderTree2vector(root->right, vec);
            vec.push_back(root->val);
            orderTree2vector(root->left, vec);
        }
    	// 取vec的第k大数即可
        int kthLargest(TreeNode* root, int k) { 
            vector<int> vec;
            orderTree2vector(root, vec);
            return vec[k-1];
        }
    };

## 五、二叉树的深度 ##

### 题目 ###

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
    提示：节点总数 <= 10000
    题目来源：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/

实例：  
![在这里插入图片描述][20210501172449681.png]

### 解析 ###

**方法：采用递归进行深度优先搜索（DFS）**

关键点： 此树的深度和其左、右子树的深度有关系。显然，此树的深度 = max (左子树的深度，右子树的深度) + 1 。

作为地推解法，关键就是要找出问题的**终止条件**以及**递推公式**，本题不难确定：

*  终止条件：当 root 为空，说明已越过叶节点，因此返回深度 0 。
 *  递推公式：树的深度 = max (左子树的深度，右子树的深度) + 1

C++实现方式如下：

class Solution { 
    public:
        int maxDepth(TreeNode* root) { 
            if(root == nullptr)
                return 0;
            int max_left = maxDepth(root->left); //左子树最大的深度
            int max_right = maxDepth(root->right); //右子树最大的深度
            return max(max_left, max_right) + 1; // 总深度 = max(左子树，右子树) + 1
        }
    };

**复杂度分析：**

*  时间复杂度 O(N)： N 为树的节点数量，计算树的深度需要遍历所有节点。
 *  空间复杂度 O(N)： 最差情况下（当树退化为链表时），递归深度可达到 N 。

**提交结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 5]

--------------------

## 六、员工的重要性 ##

### 题目 ###

给定一个保存员工信息的数据结构，它包含了员工唯一的 id ，重要度和直系下属的 id 。
    
    比如，员工 1 是员工 2 的领导，员工 2 是员工 3 的领导。他们相应的重要度为 15 , 10 , 5 。
    那么员工 1 的数据结构是 [1, 15, [2]] ，员工 2的 数据结构是 [2, 10, [3]] ，员工 3 的数据结构是 [3, 5, []] 。
    注意虽然员工 3 也是员工 1 的一个下属，但是由于 并不是直系 下属，因此没有体现在员工 1 的数据结构中。
    
    现在输入一个公司的所有员工信息，以及单个员工 id ，返回这个员工和他所有下属的重要度之和。
    
    示例：
    输入：[[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
    输出：11
    解释：
    员工 1 自身的重要度是 5 ，他有两个直系下属 2 和 3 ，而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5 + 3 + 3 = 11 。
    
    提示：
    一个员工最多有一个直系领导，但是可以有多个直系下属员工数量不超过 2000 。
    
    原题链接：https://leetcode-cn.com/problems/employee-importance/

### 题解 ###

**方法：** 采用递推的方法，显然，当前 id 员工和他所有下属的重要度之和 = 自身重要性 + 下属重要性之和；进一步，下属重要性 = 下属本身的重要性 + 下属的下属的重要性之和。

/* // Definition for Employee. class Employee { public: int id; int importance; vector<int> subordinates; }; */
    
    class Solution { 
    public:
        int getImportance(vector<Employee*> employees, int id) { 
            for(int i=0; i<employees.size(); ++i) //找到指定id的员工
            { 
                if(employees[i]->id==id)
                { 
                    if(employees[i]->subordinates.size()==0) //如果该id员工没有下属，即返回自身的重要性
                        return employees[i]->importance;
                    else // 否则，重要性 = 自身重要性 + 下属重要性之和
                    { 
                        int sum=employees[i]->importance;
                        for(int j=0; j<employees[i]->subordinates.size(); ++j)
                        { 
                            sum += getImportance(employees, employees[i]->subordinates[j]);
                        }
                        return sum;
                    }
                }
            }
            return 0; //如果员工信息数组是空的，则直接返回0
        }
    };

**提交结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 6]

## 七、平衡二叉树 ##

### 题目 ###

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 7]

### 题解 ###

此题可拆分为两个小问题：(1) 求任意二叉树的深度 (2) 判断是否是平衡二叉树

很显然，在求解这两个小问题中，都需要用到迭代的思想：

*  其中，第一问在第五题中以及详细解析
 *  第二问，关键点在于判断是平衡二叉树的条件：**二叉树中任意节点的左右子树的深度相差不超过1**。因此，不仅要根节点所在的二叉树满足条件，其左右子树也必须满足条件。

class Solution { 
    public:
        bool isBalanced(TreeNode* root) { 
            if(root==nullptr)// 如果此树为空，那么也认为此树是平衡二叉树
                return true;
            int left_depth = depth(root->left); // 获得左子树的深度
            int right_depth = depth(root->right); // 获得右子树的深度
            // 当左右子树的深度相差不超过1, 且左右子树也满足平衡二叉树的要求
            if(abs(left_depth-right_depth)<=1 && isBalanced(root->left) && isBalanced(root->right))
                return true;
            else
                return false;
        }
    
        // 获得二叉树的深度
        int depth(TreeNode* root)
        { 
            if(root==nullptr) return 0;
            return max(depth(root->left), depth(root->right))+1;
        }
    };

--------------------

## 八、对称二叉树 ##

### 题目 ###

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
    限制：0 <= 节点个数 <= 1000

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 8]

### 题解 ###

对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，**理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树）**，所以在递归遍历的过程中，也是要同时遍历两棵树。

比较的是两个子树是否对称，关键是比较两子树的里侧和外侧的元素是否相等。如图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 9]  
**递归的具体做法如下：**

1.  **确定递归函数的参数和返回值**。因为我们要比较的是根节点的两个子树是否是相互对称的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点，返回值自然是bool类型。代码如下：`bool compare(TreeNode* L, TreeNode* R)`
2.  **迭代确定终止条件**。有两种情况：(1) 有一个节点为空，则不对称，返回false，直接退出迭代 (2) 左右节点值不一样，不对称
3.  **确定递归公式或递推逻辑**。由于本题没有明显的递推公式，所以需要找出严密的递推逻辑，也就是：**判断是两个子树是否对称，关键是比较两子树的里侧和外侧的元素是否分别相等**。左右子树的里侧分别是：L->left 和 R->right；右侧分别是：L->right 和 R->left。

**C++ 实现代码如下：**

class Solution { 
    public:
        bool isSymmetric(TreeNode* root) { 
            if(root==nullptr) 
                return true;
            // 比较根节点的左子树与右子树
            return compare(root->left, root->right);
        }
    
        // 比较
        bool compare(TreeNode* L, TreeNode* R)
        { 
            // 如果左节点和右节点都是空的，则返回true
            if(L==nullptr && R==nullptr) return true;
            // 如果左、右节点有一个是空的，或者左右节点的值不一样，则表明不对称
            if(L==nullptr || R==nullptr || L->val!=R->val) return false;
            // 如果以上情况均没出现，再判断二叉树内测和外侧是否相等
            return compare(L->left, R->right) && compare(L->right, R->left);
        }
    };

## 九、二叉树的镜像 ##

### 题目 ###

请完成一个函数，输入一个二叉树，该函数输出它的镜像。
    限制：0 <= 节点个数 <= 1000

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 10]

### 题解 ###

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    
    class Solution { 
    public:
        TreeNode* mirrorTree(TreeNode* root) { 
            if (root == nullptr) return nullptr;
            TreeNode* tmp = root->left;
            root->left = mirrorTree(root->right);
            root->right = mirrorTree(tmp);
            return root;
        }
    };

[Link 1]: https://ai-wx.blog.csdn.net/article/details/115610626
[Link 2]: https://ai-wx.blog.csdn.net/article/details/116152346
[Link 3]: https://ai-wx.blog.csdn.net/article/details/116075336
[1]: /images/20221022/164c30e0cd01493e80f74a935e16ef43.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]: /images/20221022/28d3b87064534e0a8fc53fabfbdc10c7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 1]: /images/20221022/2fdb632a0f804678811b898878f3137d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 2]: /images/20221022/ffcf96fdb951440d92f60413c4127541.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 3]: /images/20221022/98caafb64feb41dea8efbe4faee9c91e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 4]: /images/20221022/d462ac417ee9462dbb876ac1233be6ac.png
[20210501172449681.png]: /images/20221022/6653cedccbad499aa73713c8a9b3baa1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 5]: /images/20221022/b2e3d0ef11924b8e954d0e978c00cd98.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 6]: /images/20221022/6c075ba1448640db9ccddf400b6fcb2d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 7]: /images/20221022/52bca4f06bab488ab7abc10b72d05e19.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 8]: /images/20221022/9ea93cfc441d4e2dbf2f1b1ef96a8ddf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 9]: /images/20221022/89d25452eefa4a48a43c9e4d8e2f0b99.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 10]: /images/20221022/c6462cf10ae24267a29f9757f2fef21e.png