本文共 1677 字，大约阅读时间需要 5 分钟。

找出BST中的第k个节点值

BST的中序遍历就是一个升序数组啊！！！！

数左子树中节点个数num，如果是k - 1个，那么当前root即为所求；如果num大于k，则从左子树中找第k个；否则从右子树中找第k - 1 - num个（即减去左子树中节点个数以及root这一个）

public class Solution {    public int kthSmallest(TreeNode root, int k) {        int num = count(root.left);        if (num >= k) {            return kthSmallest(root.left, k);        } else if (num + 1 < k) {            // 注意第二个参数            return kthSmallest(root.right, k - 1 - num);        }        return root.val;    }    private int count(TreeNode root) {        if (root == null) {            return 0;        }        return 1 + count(root.left) + count(root.right);    }}

注意dfs的时候函数调用的时候就要保证root不是null，这样里面就不用判断了

递归二叉树的中序遍历

public class Solution {    int count = 0;    int num = 0;    public int kthSmallest(TreeNode root, int k) {        count = k;        dfs(root);        return num;    }    private void dfs(TreeNode root) {        if (root.left != null) {            dfs(root.left);        }        count--;        if (count == 0) {            num = root.val;            return;        }        if (root.right != null) {            dfs(root.right);        }    }}

非递归二叉树的中序遍历

public class Solution {    public int kthSmallest(TreeNode root, int k) {        Stack
   
     stack = new Stack();        TreeNode cur = root;        while (cur != null || !stack.isEmpty()) {            while (cur != null) {                stack.push(cur);                cur = cur.left;            }            if (!stack.isEmpty()) {                cur = stack.pop();                k--;                if (k == 0) {                    return cur.val;                }                cur = cur.right;            }        }        return -1;    }}
   

转载地址：http://rahld.baihongyu.com/