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

62. 二叉搜索树的第 k 个结点

题目描述

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

法一：

非递归中序遍历

TreeNode* KthNode(TreeNode* pRoot, int k)
{
    // 采用中序遍历这个树，遍历到第k个结点就是答案
    stack<TreeNode*> s;
    int cnt = 0;
    TreeNode* cur = pRoot;
    while(cur || !s.empty()){
        while(cur){
            s.push(cur);
            cur = cur->left;
        }
        // 访问根节点
        cur = s.top();
        s.pop();
        cnt++;
        if(cnt == k)
            return cur;
        cur = cur->right;
    }
    return NULL;
}

法二：

将所有的结点按中序遍历的顺序存入一个ArrayList, 最后取出 第 k 个元素即可

 1 import java.util.ArrayList;
 2 public class Solution {
 3      // 将所有的结点按中序遍历的顺序存入一个ArrayList, 最后取出 第 k 个元素即可
 4     ArrayList<TreeNode> arr = new ArrayList<>();
 5     TreeNode KthNode(TreeNode pRoot, int k)
 6     {
 7         if(pRoot == null)
 8             return null;
 9         inOrder(pRoot);
10         if(k >= 1 && k <= arr.size())    // 如果 k 在 1 和 最大结点数之间
11             return arr.get(k - 1);
12         return null;        // 说明 k 超过了节点数
13     }
14     
15     void inOrder(TreeNode root){
16         if(root != null){
17             inOrder(root.left);
18             arr.add(root);
19             inOrder(root.right);
20         }
21     }
22 }