Day32——二叉树专题

妖狐艹你老母 2024-04-01 18:47 63阅读 0赞

#### 文章目录 ####

*   *   *   *  28.删除二叉搜索树的节点
             *  29.修剪二叉搜索树
             *  30.将有序数组转换为二叉搜索树
             *  31. 把二叉搜索树转换为累加树

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

##### 28.删除二叉搜索树的节点 #####

题目链接：[450. 删除二叉搜索树中的节点 - 力扣（LeetCode）][450. _ - _LeetCode]

*  如果目标节点大于当前节点值，则去右子树中删除；
 *  如果目标节点小于当前节点值，则去左子树中删除;
 *  如果目标节点就是当前节点，分为以下三种情况：
    
     *  其无左子：其右子顶替其位置，删除了该节点；
     *  其无右子：其左子顶替其位置，删除了该节点；
     *  其左右子都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替了其位置，并且删除该节点；
        
        **左右子树都有的情况**：
        
        ![image-20221115090229467][]

**代码实现**：

class Solution {
        
        public TreeNode deleteNode(TreeNode root, int key) {
        
            return dfs(root, key);
        }
        public TreeNode dfs(TreeNode root, int key){
        
            if(root == null){
        
                return null;
            }
    
            if(root.val > key) root.left = dfs(root.left, key);
            else if(root.val < key) root.right = dfs(root.right, key);
            else{
        // 当前节点是要删除的节点
                if(root.left == null) return root.right;// 情况1：左子树为空
                if(root.right == null) return root.left;// 情况2：右子树为空
    
                // 情况3：左右都不为空
                TreeNode node = root.right;
                while(node.left != null){
        // 找出右子树最左的节点
                    node = node.left;
                }
                node.left = root.left;// 删除欲删除节点 拼接
                root = root.right;// 跟换删除后树的根节点
            }
    
            // 递归完整结束后 返回根节点
            return root;
        }
    }

##### 29.修剪二叉搜索树 #####

**题目链接**：[669. 修剪二叉搜索树 - 力扣（LeetCode）][669. _ - _LeetCode]

**思路**：

*  root的元素值为null，直接返回null

if(root == null){
        
                return null;
            }

*  root.val < low,递归右子树，并返回右子树符合条件的头节点

if(root.val<low){
        
                return dfs(root.right,low,high);
            }

*  root.val > high,递归左子树，并返回左子树符合条件的头节点

if(root.val>high){
        
                return dfs(root.left,low,high);
            }

*  接下来将下一层处理完左子树结果赋值给root->left，右子树结果赋值给root->right。最后返回root

root.left = dfs(root.left,low,high);
            root.right = dfs(root.right,low,high);
    
            return root;

**代码实现**：

class Solution {
        
        public TreeNode trimBST(TreeNode root, int low, int high) {
        
            return dfs(root,low,high);
        }
        public TreeNode dfs(TreeNode root, int low, int high){
        
            if(root==null){
        
                return null;
            }
            if(root.val<low){
        
                return dfs(root.right,low,high);
            }
            if(root.val>high){
        
                return dfs(root.left,low,high);
            }
            root.left = dfs(root.left,low,high);
            root.right = dfs(root.right,low,high);
    
            return root;
        }
    }

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

**题目链接**：[108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）][108. _ - _LeetCode]

**思路**：

*  确定递归终止条件

if(left>right) return null;

*  确定单层递归逻辑

int mid = (right + left)/2;
            TreeNode root = new TreeNode(nums[mid]);
            root.left = dfs(nums,left,mid-1);
            root.right = dfs(nums,mid+1,right);
            return root;

**代码实现**：

class Solution {
        
        public TreeNode sortedArrayToBST(int[] nums) {
        
            return dfs(nums,0,nums.length-1);
        }
        public TreeNode dfs(int[] nums, int left, int right){
        
            if(left > right){
        
                return null;
            }
            int mid = (right + left)/2;
            TreeNode root = new TreeNode(nums[mid]);
            root.left = dfs(nums,left,mid-1);
            root.right = dfs(nums,mid+1,right);
            return root;
        }
    }

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

题目链接：[538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）][538. _ - _LeetCode]

**思路**：

*  递归函数参数以及返回值

定义一个全局变量pre，用来保存cur节点的前一个节点的数值，定义为int型就可以了

int pre = 0;
     public TreeNode convertBST(TreeNode root) {
        
     }

*  确定终止条件

if(root==null) return;

*  确定单层递归的逻辑

//右中左
            dfs(root.right);
            root.val+=pre;
            pre = root.val;
            dfs(root.left);
            return root;

**代码实现**:

class Solution {
        
        int pre = 0; 
        public TreeNode convertBST(TreeNode root) {
        
            return dfs(root);
        }
        public TreeNode dfs(TreeNode root){
        
            if(root==null){
        
                return null;
            }
            //右中左
            dfs(root.right);
            root.val+=pre;
            pre = root.val;
            dfs(root.left);
            return root;
        }
    }

[450. _ - _LeetCode]: https://leetcode.cn/problems/delete-node-in-a-bst/
[image-20221115090229467]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/dd021ef6a7d545b59bc9894df4fa9e05.png
[669. _ - _LeetCode]: https://leetcode.cn/problems/trim-a-binary-search-tree/
[108. _ - _LeetCode]: https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
[538. _ - _LeetCode]: https://leetcode.cn/problems/convert-bst-to-greater-tree/