剑指offer—二叉搜索树第k个节点 解答

剑指offer—二叉搜索树第k个节点

题目描述

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

思路

  • 我们可以想到中序遍历的结果就是该题目的序列

维护一个计数器,遍历到第k个节点的时候返回该节点

代码

public class Solution {
    TreeNode KthNode(TreeNode root, int k){
        if(root==null||k==0) return null;
        dfs(root,k);
        return kn;
    }
    TreeNode kn = null;
    int n = 0;
    public void dfs(TreeNode node,int k){
        if(node==null) return;
        dfs(node.left,k);
        if(k==(++n)){
            kn = node;
            return;
        }
        dfs(node.right,k);
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/bst-kth-node.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!