剑指offer：二叉搜索树的第k个结点

女爷i 2021-06-24 16:10 317阅读 0赞

**试题：**  
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。  
**代码：**  
二叉搜索树具有左子节点的值小于根节点，右子节点的值大于根节点。那么我们只要按中序遍历就可以排好序。

/*
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        int count = 0;
        TreeNode KthNode(TreeNode pRoot, int k)
        {
            if(pRoot!=null){
                TreeNode node = KthNode(pRoot.left, k);
                if(node!=null) return node;
                if(++count==k) return pRoot;
                node = KthNode(pRoot.right, k);
                if(node!=null) return node;
            }
            return null;
        }
    
    
    }

非递归版本：  
广度搜索一般需要借助队列结构；深度搜索一般借助栈结构。

TreeNode KthNode(TreeNode root, int k){
            if(root==null||k==0)
                return null;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            int count = 0;
            TreeNode node = root;
            do{
                if(node!=null){
                    stack.push(node);
                    node = node.left;
                }else{
                    node = stack.pop();
                    count++;
                    if(count==k)
                        return node;
                    node = node.right;
                }
            }while(node!=null||!stack.isEmpty());
            return null;
        }