【二叉树】剑指offer 54 二叉搜索树的第k个结点

描述

给定一棵结点数为 n 二叉搜索树，请找出其中的第 k 小的TreeNode结点。

数据范围：$0\le n<=100$，$0\le k\le 100$，树上每个结点的值满足$0\le val\le 100$
要求：空间复杂度 O(1)，时间复杂度 O(n)

例如，输入：{5,3,7,2,4,6,8},3， 输出4

---

题解

二叉搜索树的性质是左孩子小于父节点，父节点小于右孩子，则中序遍历为有序的，需要利用该条件来求解。

中序遍历法

思想是通过中序遍历二叉树，保存第k小的节点，需要用一个全局计数变量k1

public class Solution {
    public static int k1;
    public static TreeNode res;

    void _fn(TreeNode node) {
        if (node == null)
            return;
        _fn(node.left);
        k1--;
        if (k1 == 0) {
            res = node;
            return;
        }
        _fn(node.right);
    }

    TreeNode KthNode(TreeNode pRoot, int k) {
        k1 = k;
        _fn(pRoot);
        return res;
    }

    public static void main(String[] args) {
        TreeNode r = new TreeNode(8);
        r.left = new TreeNode(6);
        r.right = new TreeNode(10);
        r.left.left = new TreeNode(5);
        r.left.right = new TreeNode(7);
        r.right.left = new TreeNode(9);
        r.right.right = new TreeNode(11);
        TreeNode res = new Solution().KthNode(r, 2);
        System.out.println(new Solution().KthNode(r, 2).val);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

栈

从当前节点开始将所有左孩子入栈，则栈顶元素为当前最小的一个节点，每次取出这个节点，并将计数值减1，然后将其右孩子作为当前节点，继续将当前节点的左孩子入栈，寻找下一个最小的节点。
注意判断越界情况，在出栈前要判断栈是否为空，为空则结束循环。

import java.util.Stack;

public class Solution {

    TreeNode KthNode(TreeNode pRoot, int k) {
        if (pRoot == null || k <= 0)
            return null;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode res = null;
        while (true) {
            while (pRoot != null) {
                stack.push(pRoot);
                pRoot = pRoot.left; // 不断将左孩子入栈
            }
            if (stack.isEmpty())
                break;
            TreeNode top = stack.pop(); //获取当前的最小值
            k--;
            if (k == 0) {
                res = top;
                break;
            }
            pRoot = top.right;
        }
        return res;
    }

    public static void main(String[] args) {
    	// 测试样例
        TreeNode r = new TreeNode(8);
        r.left = new TreeNode(6);
        r.right = new TreeNode(10);
        r.left.left = new TreeNode(5);
        r.left.right = new TreeNode(7);
        r.right.left = new TreeNode(9);
        r.right.right = new TreeNode(11);
        TreeNode res = new Solution().KthNode(r, 8);
        System.out.println(res);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40