《剑指offer》第62题 二叉搜索树的第k个结点

题目描述

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

解题思路

思路一：递归

//思路：二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。
//     所以，按照中序遍历顺序找到第k个结点就是结果。
public class Solution {
   int index = 0; //计数器
    TreeNode KthNode(TreeNode root, int k)
    {
        if(root != null){ //中序遍历寻找第k个
            //上面判断递归截止条件
            TreeNode node = KthNode(root.left,k);
            if(node != null)// 左子树中找到符合要求的节点返回
                return node;
            index ++;
            if(index == k)
                return root;
            node = KthNode(root.right,k);
            if(node != null)//左子树中没有找到，在右子树找到了符合要求的节点返回
                return node;
        }
        return null;
    }
}

思路二：非递归

import java.util.*;
public class Solution {
    TreeNode KthNode(TreeNode root, int k) {
        if(root == null || k == 0) return null;
        int count = 0;
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || ! stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            count ++;
            if(count == k) return root;
            root = root.right;
        }
        return null;
    }
}

代码三：

/*
 *中序遍历二叉搜索树后正好是从小到大的顺序，直接返回第k-1个即可
 */
import java.util.ArrayList;
public class Solution {
    ArrayList<TreeNode> treenode=new ArrayList<TreeNode>();
    TreeNode KthNode(TreeNode pRoot, int k) {
        InOrder(pRoot);
        if(treenode.size()<1||k<1||k>treenode.size())
            return null;
        return treenode.get(k-1);

    }
    public void InOrder(TreeNode node)
    {
        if(node!=null)
        {
            InOrder(node.left);
            treenode.add(node);
            InOrder(node.right);
        }
    }
}

参考资料

https://www.nowcoder.com/questionTerminal/ef068f602dde4d28aab2b210e859150a?f=discussion