LeetCode 669. 修剪二叉搜索树

Categories:

题目描述
思路分析
1. 解法一：递归裁剪（推荐）
相似题目

题目描述

✅ 669. 修剪二叉搜索树

思路分析

解法一：递归裁剪（推荐）

核心思路：

若节点值小于 low，则整棵左子树都被裁掉，返回裁剪后的右子树。

若节点值大于 high，则整棵右子树都被裁掉，返回裁剪后的左子树。

否则递归裁剪左右子树并连接。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(h)，其中 h 表示树高。

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }

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

        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;
    }
}

func trimBST(root *TreeNode, low int, high int) *TreeNode {
	if root == nil {
		return nil
	}

	if root.Val < low {
		return trimBST(root.Right, low, high)
	}

	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
}

相似题目

题目	难度	考察点
450. 删除二叉搜索树中的节点	中等	BST 操作
701. 二叉搜索树中的插入操作	中等	BST 操作
98. 验证二叉搜索树	中等	BST
538. 把二叉搜索树转换为累加树	中等	BST 遍历
700. 二叉搜索树中的搜索	简单	BST 查找

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/52815758