剑指Offer - 62 - 二叉搜索树的第k个结点.md

剑指Offer - 62 - 二叉搜索树的第k个结点

题目链接

https://www.nowcoder.com/practice/ef068f602dde4d28aab2b210e859150a?tpId=13&tqId=11215&tPage=4&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking

题目

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）    中，按结点数值大小顺序第三小结点的值为4。

解析

这题目也不难，二叉搜索树中序遍历是升序的，可以中序遍历然后计数即可。

非递归中序不懂的可以看这篇博客。

import java.util.*;

public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = pRoot;
        int cnt = 0;
        while(!stack.isEmpty() || p != null){
            while(p != null){
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            cnt++;
            if(k == cnt) 
                return p;
            p = p.right;
        }
        return null;
    }
}

递归可能稍微有点难以理解。

要注意的是， 先走到最左边，最下面如果没有到达k，就直接返回null，即可，只有在k == cnt的时候，才会返回找到的节点。

import java.util.*;

public class Solution {
    int cnt;
    
    TreeNode KthNode(TreeNode pRoot, int k) {
        return in(pRoot, k);
    }
    
    private TreeNode in(TreeNode node, int k) {
        if (node == null) return null;
        TreeNode L = in(node.left, k);
        if (L != null) return L;//之前已经找到了
        return ++cnt == k ? node : in(node.right, k);
    }
}