一、題目大意
給你二叉搜索樹的根節點 root ，同時給定最小邊界low 和最大邊界 high，通過修剪二叉搜索樹，使得所有節點的值在[low, high]中，修剪樹 不應該 改變保留在樹中的元素的相對結構 (即，如果沒有被移除，原有的父代子代關系都應當保留)， 可以證明，存在 唯一的答案 ，
所以結果應當回傳修剪好的二叉搜索樹的新的根節點，注意，根節點可能會根據給定的邊界發生改變，
示例 1：
輸入：root = [1,0,2], low = 1, high = 2
輸出：[1,null,2]
示例 2：
輸入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
輸出：[3,2,null,1]
提示：
-
樹中節點數在范圍 [1, 104] 內
-
0 <= Node.val <= 104
-
樹中每個節點的值都是 唯一 的
-
題目資料保證輸入是一棵有效的二叉搜索樹
-
0 <= low <= high <= 104
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/trim-a-binary-search-tree
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
二、解題思路
什么是二叉查找樹？
二叉查找樹（Binary Search Tree，BST）是一種特殊的二叉樹：對于每個父節點，其左子樹中所有節點的值小于等于父節點的值，其右子樹中所有節點的值大于等于父節點的值，
利用二叉查找樹的大小關系，我們可以很容易地利用遞回進行樹的處理，
三、解題方法
3.1 Java實作
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null) {
return root;
}
if (root.val > high) {
return trimBST(root.left, low, high);
}
if (root.val < low) {
return trimBST(root.right, low, high);
}
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
}
四、總結小記
- 2022/9/24 孩子靜悄悄，必定在做妖；老人也是
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/509429.html
標籤：其他
上一篇：游戲的AI型別