摘要:题目意思就是要一个个的返回当前的最小值。所以解法自然就是。我们需要找出被打乱的点并返回正确结果。然后将两个不正确的点记录下来,最后回原来正确的值。如果是叶子节点,或者只有一个子树。思想来自于的代码实现。
跳过总结请点这里:
https://segmentfault.com/a/11...
BST最明显的特点就是root.left.val < root.val < root.right.val.
还有另一个特点就是,bst inorder traversal result is an ascending array.
下面简单表示一个BST:
60 / 40 80 / / 20 50 70 90 / 10 30 100
BST inorder traversal result is: 10 20 30 40 50 60 70 80 90 100.
BST 和普通的树的区别就在于它是一个有序的,为了保证顺序,我们需要通过inorder traversal得到,所以几乎所有leetcode关于bst的题目,都是在考我们如何利用inorder traverse.
简单题目只过代码思路,代码会附在题号底下,为了减少博客篇幅,题目描述细节请参看leetcode。
LC 173 Binary Search Tree Iterator.
Calling next() will return the next smallest number in the BST.
题目意思就是要一个个的返回bst当前的最小值。强提示:有序。
所以解法自然就是bst inorder traverse。起点就是BST里最小的值,也就是leftmost.
public class BSTIterator { ArrayDequestk; public BSTIterator(TreeNode root) { stk = new ArrayDeque (); pushAll(root); } /** @return whether we have a next smallest number */ public boolean hasNext() { return !stk.isEmpty(); } /** @return the next smallest number */ public int next() { TreeNode node = stk.pop(); if(node.right !=null) { pushAll(node.right); } return node.val; } public void pushAll(TreeNode node){ while(node != null){ stk.push(node); node = node.left; } } }
新增了预处理的方法。这个方法的好处就是每次next()都是严格的O(1), 而上面那个方法只是AVE O(1).
public class BSTIterator { ArrayListascending; int pos = 0; public BSTIterator(TreeNode root) { ascending = new ArrayList (); inorder(root, ascending); } /** @return whether we have a next smallest number */ public boolean hasNext() { return pos < ascending.size(); } /** @return the next smallest number */ public int next() { return ascending.get(pos++); } public void inorder(TreeNode root, ArrayList ascending){ if(root == null) return; inorder(root.left, ascending); ascending.add(root.val); inorder(root.right, ascending); } }
LC 230 Kth Smallest Element in a BST
返回BST里第k小的元素。 强提示:有序。
从leftmost开始,找到第k个点返回。时间复杂度近似到O(K).
为了写代码的清晰度,我们使用recursion的方法做inorder traversal。
public class Solution { public int kthSmallest(TreeNode root, int k) { if(root == null) return 0; int[] res = {Integer.MIN_VALUE}; kthSmallest(root, k, res); return res[0]; } public int kthSmallest(TreeNode root, int k, int[] res){ if(res[0] != Integer.MIN_VALUE || root == null){ //if finded kth, all recursion will immediately return to root. return 0; } int left = kthSmallest(root.left, k,res); if(left == k-1){ res[0] = root.val; } int right = kthSmallest(root.right, k - left -1, res); return left + right + 1;
LC99 Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake.
如果BST中有两个节点位置互相交换了,怎么办? 表明BST的顺序被打乱。我们需要找出被打乱的点并返回正确结果。
利用上面给的BST的图,我们swap(20, 90),得到如下BST:
60 / 40 80 / / 90 50 70 20 / 10 30 100
inorder traversal result is:
10 90 30 40 50 60 70 80 20 100
this is not an ascending array.
90 >30, 80 >20 这两处顺序不合理,靠前的值大于靠后的值。
所以这里我们在inorder traversal的同时,我们还需要比较pre.val和cur.val。
然后将两个不正确的点记录下来,最后swap回原来正确的值。
public class Solution { private TreeNode firstNode = null; private TreeNode secondNode = null; private TreeNode preNode = new TreeNode(Integer.MIN_VALUE); public void recoverTree(TreeNode root) { if(root == null) return; inorderTraversal(root); int temp = firstNode.val; firstNode.val = secondNode.val; secondNode.val = temp; } public void inorderTraversal(TreeNode root){ if(root == null) return; inorderTraversal(root.left); if(firstNode == null && preNode.val > root.val) { firstNode = preNode; } if(firstNode != null && preNode.val > root.val) { secondNode = root; } preNode = root; inorderTraversal(root.right); } }
LC450 Delete Node in a BST
找到一个点容易,利用root.left.val < root.val < root.right.val,时间复杂度O(logN)找到。
删除一个点。如果是叶子节点,或者只有一个子树。都容易操作。
如果是中间节点怎么办?我们找到它在bst里的前一个点(或者后一个点),改变要删除节点的值,然后删除它的前一个点。
思想来自于heap的代码实现。我们每次Pop的时候取的是根节点的值,然后把heap里最尾端的点换到根节点,然后shift down。
public class Solution { public TreeNode deleteNode(TreeNode root, int key) { if(root == null) return null; if(key < root.val) { root.left = deleteNode(root.left, key); } else if(key > root.val) { root.right = deleteNode(root.right, key); } else { if(root.left == null) { return root.right; } else if(root.right == null) { return root.left; } TreeNode node = findNextMin(root.right); root.val = node.val; root.right = deleteNode(root.right, node.val); } return root; } public TreeNode findNextMin(TreeNode node) { while(node.left != null) { node = node.left; } return node; } }
写不下了,换一篇,点这里:
https://segmentfault.com/a/11...
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/66574.html
摘要:当我们希望查询时,则从根节点开始寻找其所在的区间,如果位于左侧区间,则查询左子树啊,如果位于右侧区间,则查询右子树。如果横跨了分割点,则分别查询左子树的部分和右子树的部分。 题目要求 You are given an integer array nums and you have to return a new counts array. The counts array has t...
摘要:题目链接的题,用来做,这种求有多少的题一般都是。里多加一个信息表示以为的节点数。也可以做,因为是统计有多少的,其实就是求从最小值到的。的是,要做一个映射,把的值映射到之间。所以先把给一下,用一个来做映射。还有的方法,参考 315. Count of Smaller Numbers After Self 题目链接:https://leetcode.com/problems... divi...
摘要:复杂度思路每遍历到一个数,就把他到已有的中。对于每一个,维护一个和一个自身的数目。比如,然后每次遍历到一个数,就把对应位置的值加一。比如碰到之后,就变成,然后统计的和。 Leetcode[315] Count of Smaller Numbers After Self ou are given an integer array nums and you have to return a...
摘要:我们建立的,其中解决重复值的问题,记录左子树的节点数。给定要找的点,这里的规律就是,往右下走,说明当前点和当前的的左子树的值全部比小。我们走到要向右,这是左子树没变化,这里也不变。 题目细节描述参看leetcode。 今天的重头戏 LC315 Count of Smaller Numbers After Self.在讲这个题目之前,请思考这个问题。在BST找到所有比Node P小的节点...
Problem You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i]. Exam...
阅读 2144·2023-04-26 00:38
阅读 1930·2021-09-07 10:17
阅读 887·2021-09-02 15:41
阅读 637·2021-08-30 09:45
阅读 541·2019-08-29 17:25
阅读 3204·2019-08-29 15:07
阅读 2182·2019-08-29 12:52
阅读 3734·2019-08-26 13:35