天天看點

二叉搜尋樹的第K個節點(思路與實作)

題目描述

給定一顆二叉搜尋樹,請找出其中的第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;
    }
}
           

繼續閱讀