題目描述
給定一顆二叉搜尋樹,請找出其中的第k小的結點。例如, 5 / \ 3 7 /\ /\ 2 4 6 8 中,按結點數值大小順序第三個結點的值為4。
思路:
首先這個是一顆二叉搜尋樹,我隻需要是的這個這顆二叉搜尋樹進行排序,然後找到第k個就可以了,那個我們都知道二叉搜尋樹的中序周遊是一個有順序的序列,這個時候我就是要中序周遊這顆二叉樹,然後設定一個變量,通路一個變量的時候就加一,判斷這個變量和k是否相等,如果相等,則将目前的這個結點傳回即可。
實作:
import java.util.Stack;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
TreeNode KthNode(TreeNode pRoot, int k)
{
//首先中序周遊這顆二叉樹
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = pRoot;
int i = 0;
while(p != null || !stack.isEmpty()){
if(p != null){
stack.push(p);
p = p.left;
}else{
TreeNode node = stack.pop();
i++;
if(i == k){
return node;
}
p = node.right;
}
}
return null;
}
}