WHCSRL 技术网

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

描述

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

数据范围: 0 ≤ n < = 100 0 le n<=100 0n<=100 0 ≤ k ≤ 100 0le k≤100 0k100,树上每个结点的值满足 0 ≤ v a l ≤ 100 0≤val≤100 0val100
要求:空间复杂度 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
推荐阅读