【剑指Offer】54. 二叉查找树的第 K 个结点

深碍√TFBOYSˉ_ 2022-12-02 04:27 108阅读 0赞

[力扣][Link 1]  
[NowCoder][]

## 解题思路 ##

利用二叉查找树中序遍历有序的特点。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
            private static int k1, res;
    
        public int kthLargest(TreeNode root, int k) { 
            k1 = k;
            // 中序遍历（递增） 左根右
            dfs(root);
            return res;
        }
    
        private static void dfs(TreeNode root) { 
            if(root == null || k1 == 0)
                return;
            // 第k大倒序
            // 右
            dfs(root.right);
            // 根
            if(--k1 == 0)
                res = root.val;
            // 左
            dfs(root.left);
        }
    }

## 题目描述 ##

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

private TreeNode ret;
    private int cnt = 0;
    
    public TreeNode KthNode(TreeNode pRoot, int k) { 
        inOrder(pRoot, k);
        return ret;
    }
    
    private void inOrder(TreeNode root, int k) { 
        if (root == null || cnt >= k)
            return;
        inOrder(root.left, k);
        cnt++;
        if (cnt == k)
            ret = root;
        inOrder(root.right, k);
    }

[Link 1]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/submissions/
[NowCoder]: https://www.nowcoder.com/practice/ef068f602dde4d28aab2b210e859150a?tpId=13&tqId=11215&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=bennyrhys