資訊專欄INFORMATION COLUMN
摘要：題目鏈接二分找結(jié)果，按左邊數(shù)來分如果改下，加入的，那就可以在時(shí)間內(nèi)找到結(jié)果了
Kth Smallest Element in a BST
題目鏈接：https://leetcode.com/problems...
inorder traverse：
public class Solution {
public int kthSmallest(TreeNode root, int k) {
// morris: inorder traverse
TreeNode cur = root, prev = null;
int count = 0;
while(cur != null) {
// reach the end of left part
if(cur.left == null) {
if(++count == k) return cur.val;
cur = cur.right;
}
else {
prev = cur.left;
// find the right most part
while(prev.right != null && prev.right != cur) prev = prev.right;
// reach the end of current right part
if(prev.right == null) {
prev.right = cur;
cur = cur.left;
}
// recover the tree
else {
prev.right = null;
if(++count == k) return cur.val;
cur = cur.right;
}
}
}
return -1;
}
}
二分找結(jié)果，按左邊nodes數(shù)來分：
public class Solution {
public int kthSmallest(TreeNode root, int k) {
int left = getNum(root.left);
if(left == k - 1) return root.val;
else if(left < k - 1) return kthSmallest(root.right, k - left - 1);
else return kthSmallest(root.left, k);
}
private int getNum(TreeNode node) {
if(node == null) return 0;
// divide and conquer
return 1 + getNum(node.left) + getNum(node.right);
}
}
如果改下node，加入number of left的field，那就可以在O(h)時(shí)間內(nèi)找到結(jié)果了：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* int leftNum;
* TreeNode(int x, int num) { val = x; leftNum = num; }
* }
*/
public class Solution {
public int kthSmallest(TreeNode root, int k) {
int left = root.leftNum;
if(left == k - 1) return root.val;
else if(left < k - 1) return kthSmallest(root.right, k - left - 1);
else return kthSmallest(root.left, k);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/66636.html
摘要：中序遍歷復(fù)雜度時(shí)間空間思路因?yàn)樽蠊?jié)點(diǎn)小于根節(jié)點(diǎn)小于右節(jié)點(diǎn)，二叉搜索樹的一個(gè)特性就是中序遍歷的結(jié)果就是樹內(nèi)節(jié)點(diǎn)從小到大順序輸出的結(jié)果。這里采用迭代形式，我們就可以在找到第小節(jié)點(diǎn)時(shí)馬上退出。這樣我們就可以用二叉樹搜索的方法來解決這個(gè)問題了。 Kth Smallest Element in a BST Given a binary search tree, write a function...
摘要：解題思路本題需要找的是第小的節(jié)點(diǎn)值，而二叉搜索樹的中序遍歷正好是數(shù)值從小到大排序的，那么這題就和中序遍歷一個(gè)情況。 Kth Smallest Element in a BSTGiven a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You ...
摘要：題目意思就是要一個(gè)個(gè)的返回當(dāng)前的最小值。所以解法自然就是。我們需要找出被打亂的點(diǎn)并返回正確結(jié)果。然后將兩個(gè)不正確的點(diǎn)記錄下來，最后回原來正確的值。如果是葉子節(jié)點(diǎn)，或者只有一個(gè)子樹。思想來自于的代碼實(shí)現(xiàn)。 跳過總結(jié)請(qǐng)點(diǎn)這里：https://segmentfault.com/a/11... BST最明顯的特點(diǎn)就是root.left.val < root.val < root.right.v...
摘要：先放一行，或一列把堆頂?shù)淖钚≡厝〕鰜恚〈?，如果該有下一行下一列的，放入堆中最小的個(gè)元素已經(jīng)在上面的循環(huán)被完了，下一個(gè)堆頂元素就是 Problem Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in...
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.Note that it is the kth smallest element in the sorted order, not the...
閱讀 1377·2021-11-15 11:37
閱讀 2684·2021-09-22 10:56
閱讀 3471·2021-09-06 15:11
閱讀 901·2021-08-31 09:45
閱讀 3027·2021-07-28 11:16
閱讀 1883·2019-08-30 15:44
閱讀 546·2019-08-30 13:22
閱讀 3403·2019-08-30 13:18
