题解 | #二叉搜索树的第k个结点#

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    
    this.right = null;
} */
function KthNode(pRoot, k)
{
    // write code here
    //特殊输入
    if(pRoot ===null || k===0){return null}
    //采用栈中序遍历，将左子树结点压入栈中，弹出栈顶项并比较弹出数和k的关系，最后去找右节点压入并弹出，若没有右节点则向上弹出直至有右节点。
    let num = 0
    let stack = []
    while(pRoot || stack.length){
        while(pRoot){
            stack.push(pRoot)
            pRoot=pRoot.left
        }
        let n = stack.pop()
        num++
        if(num === k) return n 
        pRoot=n.right
    }
    
}
module.exports = {
    KthNode : KthNode
};