LeetCode数据结构基础---2021/8/25

布满荆棘的人生 2022-09-08 03:45 120阅读 0赞

### 目录 ###

*  将有序数组转换为二叉搜索树
 *  从前序与中序遍历序列构造二叉树
 *  二叉树的锯齿形层序遍历
 *  二叉树的右视图
 *  路径总和 II
 *  删除二叉搜索树中的节点

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]  
分析：  
  BST的中序遍历是升序的，本题要求高度平衡，因此我们需要选择升序序列的中间元素作为根节点，然后将其左边作为左子树，右边作为右子树，递归建树。  
代码：

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

[根据遍历序列递归创建二叉树][Link 1]

# 二叉树的锯齿形层序遍历 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]  
分析：  
  简单的层序遍历，可以设置一个flag来调整每一层遍历的顺序。  
代码：

/** * 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) { 
            vector<vector<int>> res;
            queue<TreeNode*> que;
            if(root == NULL) { 
                return res;
            }
            que.push(root);
            int flag = 1;
            vector<int> temp;
            while(!que.empty()) { 
                int n = que.size();
                for(int i = 0; i < n; i++) { 
                    TreeNode* p = que.front();
                    que.pop();
                    temp.push_back(p->val);
                    if(p->left) { 
                        que.push(p->left);
                    }
                    if(p->right) { 
                        que.push(p->right);
                    }
                }
                if(flag) { 
                    flag = 0;
                }else { 
                    reverse(temp.begin(), temp.end());
                    flag = 1;
                }
                res.push_back(temp);
                temp.clear();
            }
            return res;
        }
    };

# 二叉树的右视图 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]  
分析：  
  右侧能看到的结点就是每一层最右边结点的集合，因此可以参考上一题，使用层序遍历，然后每一层只保存最右边的结点。  
代码：

/** * 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> rightSideView(TreeNode* root) { 
            vector<int> res;
            queue<TreeNode*> que;
            if(root == NULL) { 
                return res;
            }
            que.push(root);
            while(!que.empty()) { 
                int n = que.size();
                for(int i = 0; i < n; i++) { 
                    TreeNode* p = que.front();
                    que.pop();
                    if(i == n - 1) { 
                        res.push_back(p->val);   //添加每层最后一个结点
                    }
                    if(p->left) { 
                        que.push(p->left);
                    }
                    if(p->right) { 
                        que.push(p->right);
                    }
                }
            }
            return res;
        }
    };

# 路径总和 II #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]  
分析：  
  简单dfs。  
代码：

# 删除二叉搜索树中的节点 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 5]  
分析：  
  分为三种情况：

1.  需要删除的是叶子结点：直接删除。
2.  需要删除的结点右子树不为空，则该结点可以由该结点的后继结点进行替代，该后继结点位于右子树中较低的位置。然后可以从后继结点的位置递归向下操作以删除后继结点。
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) {} * }; */
    class Solution { 
    private:
        TreeNode* successor(TreeNode* root) { 
            TreeNode* cur = root->right;
            while(cur->left) { 
                cur = cur->left;
            }
            return cur;
        }
    
        TreeNode* predecessor(TreeNode* root) { 
            TreeNode* cur = root->left;
            while (cur->right) { 
                cur = cur->right;
            }
            return cur;
        }
    public:
        TreeNode* deleteNode(TreeNode* root, int key) { 
            if(root == NULL) { 
                return NULL;
            }
            if(root->val > key) { 
                root->left = deleteNode(root->left, key);
            }else if(root->val < key) { 
                root->right = deleteNode(root->right, key);
            }else { 
                if(root->left == NULL && root->right == NULL) { 
                    delete root;
                    root = NULL;
                }else if(root->right) { 
                    root->val = successor(root)->val;
                    root->right = deleteNode(root->right, root->val);
                }else { 
                    root->val = predecessor(root)->val;
                    root->left = deleteNode(root->left, root->val);
                }
            }
            return root;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]: /images/20220829/7cf17e1efb5c430a998c16288ac73eba.png
[Link 1]: https://blog.csdn.net/Cyril_KI/article/details/119830482
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]: /images/20220829/a501a98285504fc38e10ed541ad07464.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]: /images/20220829/b38a6c81015a4f82a603a563495f07ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]: /images/20220829/3c7048d4acdd43d99ecd145fc20a0124.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 4]: /images/20220829/cdfeb87a52d44a15924c93d08ef5c7f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 5]: /images/20220829/c9ca05ff29704b899dd1bba32c1a3196.png