Leetcode 热题100之二叉树2

1.二叉树的层序遍历

思绪分析：层序遍历是逐层从左到右访问二叉树的全部节点，通常可以使用广度优先搜索（BFS）来实现。我们可以使用一个队列（FIFO）来存储每一层的节点，并逐层访问。

• 初始化队列：将根节点放入队列中。如果根节点为空，则返回空结果；
  
• 层级遍历：当队列不为空时，表现尚有节点须要访问，每次处置处罚一层
  
  
  
  • 获取当前层的节点数目‘
    
  • 遍历当前层的全部节点，将节点值存入结果列表；
    
  • 将当前节点的左右节点加入队列，供下一层使用；
    
  
  
• 返回结果：将每一层的节点值依次存入结果列表并返回。
  

详细实当代码（详解版）：

1. /**
2. * Definition for a binary tree node.
3. * struct TreeNode {
4. *     int val;
5. *     TreeNode *left;
6. *     TreeNode *right;
7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10. * };
11. */
12. class Solution {
13. public:
14.     vector<vector<int>> levelOrder(TreeNode* root) {
15.         vector<vector<int>> result;//存储层序遍历结果
16.         if(root == nullptr) return result;//空树
18.         queue<TreeNode*> q;//队列用于广度优先搜索
19.         q.push(root);
21.         while(!q.empty()){
22.             int levelSize = q.size();//当前层的节点梳理
23.             vector<int> currentLevel;//存储当前层的节点值
25.             for(int i = 0 ; i < levelSize ; i ++){
26.                 TreeNode* node = q.front();//取出队首节点
27.                 q.pop();//移除队首节点
28.                 currentLevel.push_back(node->val);//添加当前节点的值道当前层
30.                 //将左右子节点加入队列，供下一层访问
31.                 if(node->left) q.push(node->left);
32.                 if(node->right) q.push(node->right);
33.             }
34.             result.push_back(currentLevel);//将当前层加入结果
35.         }
36.         return result;
37.     }
38. };

复制代码

• 时间复杂度：O(n),此中n是节点总数。每个节点访问一次
  
• 空间复杂度：O(n),队列在最坏情况下大概会存储全部叶节点。
  

2.将有序数组转化为二叉搜索树

思绪分析：将一个已排序的整数数组转换为平衡的二叉搜索树（BST）可以通过递归的方法完成。这个题目的关键在于，平衡的二叉搜索树要求左右子树的高度差不高出 1，这可以通过将数组的中心元素作为根节点来实现，左半部门构成左子树，右半部门构成右子树。如许递归下去，可以构造出一个平衡的 BST。

• 选择中心元素：为了让树平衡，应该选择数组的中心元素作为根节点；
  
• 递归构建左右子树：将左半部门的数组递归构建左子树，右半部门的数组递归构建为右子树。
  
• 克制条件：当子数组为空时，返回nullptr。
  

详细实当代码（详解版）：

1. // 辅助函数：递归构建平衡二叉搜索树
2. TreeNode* buildBST(const vector<int>& nums, int left, int right) {
3.     // 终止条件：当左边界超过右边界时，返回空指针
4.     if (left > right) return nullptr;
5.    
6.     // 选择中间元素作为根节点
7.     int mid = left + (right - left) / 2;
8.     TreeNode* root = new TreeNode(nums[mid]);
9.    
10.     // 递归构建左子树
11.     root->left = buildBST(nums, left, mid - 1);
12.    
13.     // 递归构建右子树
14.     root->right = buildBST(nums, mid + 1, right);
15.    
16.     // 返回当前子树的根节点
17.     return root;
18. }
20. // 主函数：将排序数组转换为平衡二叉搜索树
21. TreeNode* sortedArrayToBST(vector<int>& nums) {
22.     return buildBST(nums, 0, nums.size() - 1);
23. }

复制代码

• 时间复杂度：O(n),其在n是数组的长度。每个元素仅访问一次，用于构建立节点；
  
• 空间复杂度：O（log n),由于递归深度与树的高度干系。对于平衡的二叉树，高度约为log(n)。
  

3.验证二叉搜索树

思绪分析：
要判定一个二叉树是否是有用的二叉搜索树（BST），可以使用 BST 的性子：

• 左子树的全部节点值必须小于当前节点的值。
  
• 右子树的全部节点值必须大于当前节点的值。
  

我们可以通过递归来查抄每个节点是否满意这个条件。在递归过程中，为每个节点维护一个允许的值范围（最小值和最大值）。对于当前节点：

• 左子节点的值应该小于当前节点的值，且在当前的最小值到当前节点值的范围内。
  
• 右子节点的值应该大于当前节点的值，且在当前节点值到当前的最大值范围内。
  

实现思绪：

• 递归查抄节点范围：在递归中为每一个节点维护一个值范围；
  
• 查抄左右子树：在每次递归时，左子树的最大值更新为当前节点的值，右子树的最小住更新为当前节点的值；
  
• 克制条件:如果节点为空，返回true；如果节点值不在指定的范围内，返回false；
  

1. /**
2. * Definition for a binary tree node.
3. * struct TreeNode {
4. *     int val;
5. *     TreeNode *left;
6. *     TreeNode *right;
7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10. * };
11. */
12. class Solution {
13. public:
14.     bool isValidBST(TreeNode* node , long long minVal , long long maxVal){
15.         if(node == nullptr) return true;
17.         //检查当前节点是否在允许的范围内
18.         if(node->val <= minVal || node->val >= maxVal) return false;
20.         //递归检测左子树和右子树
21.         //左子树的最大值更新为当前节点的值
22.         //右子树的最小值更新为当前节点的值
23.         return isValidBST(node->left,minVal,node->val)
24.          && isValidBST(node->right,node->val,maxVal);
25.     }
26.     bool isValidBST(TreeNode* root) {
27.         return isValidBST(root,LONG_LONG_MIN,LONG_LONG_MAX);
28.     }
29. };

复制代码

• 时间复杂度：O(n),此中n是节点总数，每个节点访问一次；
  
• 空间复杂度：O(h),其在h是树的高度。
  

4.二叉搜索树中第k小的元素

思绪分析：在二叉搜索树（BST）中，第 k 小的元素可以通过 中序遍历得到，由于中序遍历的结果是按升序分列的。在中序遍历中，只需计数到第 k 个节点即可找到所需的元素。

• 中序遍历：由于二叉搜索树的性子，中序遍历（左根右）会以升序遍历节点；
  
• 计数节点：在中序遍历时，每访问一个节点，增长计数器。当计数器即是k时，当前节点即为第k小的节点
  
• 剪枝：当找到第k小的节点后，可以克制遍历，节流不须要的运算。
  

详细实当代码（详解版）：

1. class Solution {
2. public:
3.     int result = 0;//存储结果
4.     int count = 0;//计数器
5.     //中序遍历
6.     void inorder(TreeNode* node,int k){
7.         if(node == nullptr) return;
9.         //遍历左子树
10.         inorder(node->left,k);
12.         //访问当前节点
13.         count ++;
14.         if(count == k){
15.             result = node->val;
16.             return;
17.         }
18.         //遍历右子树
19.         inorder(node->right,k);
20.     }
21.     int kthSmallest(TreeNode* root, int k) {
22.         inorder(root,k);
23.         return result;
24.     }
25. };

复制代码

• 时间复杂度：O(h+k），此中h是树的高度，最坏情况下须要遍历k个节点；
  
• 空间复杂度：O(h)，递归调用栈的最大深度和树的高度成正比。
  

5.二叉树的右视图

思绪分析：要从二叉树的右侧查察节点值，可以使用 层序遍历，即逐层遍历二叉树。对于每一层的最右侧节点，将其加入结果列表。我们可以通过 广度优先搜索（BFS） 来实现该过程，由于 BFS 可以方便地按层处置处罚节点。

• 层序遍历：使用队列举行广度优先搜索，从根节点开始按层遍历树；
  
• 纪录每层的最右节点：在遍历每一层的节点时，末了一个访问的节点即为该层的最右侧欢迎你，将其添加到结果中；
  
• 继续下一层：继续处置处罚下一层，知道全部节点都被遍历完。
  

详细实当代码（详解版）：

1. class Solution {
2. public:
3.     vector<int> rightSideView(TreeNode* root) {
4.         vector<int> result;  // 存储右视图的结果
5.         if (root == nullptr) return result;  // 如果根节点为空，返回空的结果
7.         queue<TreeNode*> q;  // 创建一个队列，用于层序遍历二叉树
8.         q.push(root);  // 将根节点加入队列，开始层序遍历
10.         // 循环，直到队列为空
11.         while (!q.empty()) {
12.             int levelSize = q.size();  // 当前层的节点数
13.             TreeNode* currentNode;
15.             // 遍历当前层的所有节点
16.             for (int i = 0; i < levelSize; ++i) {
17.                 currentNode = q.front();  // 获取队首节点
18.                 q.pop();  // 弹出队首节点
19.                
20.                 // 如果存在左子节点，则将其加入队列
21.                 if (currentNode->left) q.push(currentNode->left);
22.                
23.                 // 如果存在右子节点，则将其加入队列
24.                 if (currentNode->right) q.push(currentNode->right);
25.             }
26.             
27.             // 当前层的最后一个节点是从右侧可以看到的节点，将其值加入结果
28.             result.push_back(currentNode->val);
29.         }
30.         
31.         return result;  // 返回右视图的结果
32.     }
33. };

复制代码

• 时间复杂度：O(n)，此中n是二叉树的节点数，每个节点都被访问一次；
  
• 空间复杂度：O(d),此中d是二叉树的最大宽度。