二叉搜索树的第k个节点

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param proot TreeNode类 
# @param k int整型 
# @return int整型
#
class Solution:
    def KthNode(self , proot: TreeNode, k: int) -> int:
        # corner case
        if not proot: return -1

        stk, trav = [], proot
        while stk&nbs***bsp;trav:
            while trav:
                stk.append(trav)
                trav = trav.left
                
            k -= 1
            if not k: return stk[-1].val
        
            trav = stk[-1].right
            stk.pop()
            
        return -1

import java.util.*;

public class Solution {
    //    由于这是一棵二叉搜索树，因此很容易考虑到直接进行中序遍历，将结果放到ArrayList中
    //    这里需要注意：ArrayList的起始角标是0，
    //    因此如果k的大小在ArrayList的容量大小范围内，返回size-1处的数值
    //    否则，返回-1
    private List<Integer> inOrderSet = new ArrayList<>();
    public int KthNode (TreeNode proot, int k) {
        //    如果是空树，或者k == 0，返回 -1
        if(proot == null || k == 0)
            return -1;
        
        //    中序遍历，结果会保存到ArrayList中
        inOrder(proot);
        
        //    如果k的大小超过了ArrayList的容量大小，返回-1
        if(k > inOrderSet.size())
            return -1;
        
        //    否则，说明k的大小在ArrayList的大小范围内，返回size-1处的数值
        return inOrderSet.get(k - 1);
    }
    
    //    中序遍历【中序遍历左，根结点，中序遍历右】
    private void inOrder(TreeNode root){
        if(root == null)
            return ;
        
        inOrder(root.left);
        inOrderSet.add(root.val);
        inOrder(root.right);
    }
}

public class Solution {
    // res -- 保存返回值，count -- 统计次数（第几小）
    int res = -1, count = 0;
    public int KthNode (TreeNode proot, int k) {
        if (proot == null) return res;
        inorder(proot, k);
        return res;
    }

    public void inorder(TreeNode proot, int k) {
        // 当遍历到节点为空或者超过k时，返回
        if (proot == null || count > k) return;
        inorder(proot.left, k);
        // 判断是否是需要的第k小
        if (++count == k) res = proot.val;
        inorder(proot.right, k);
    }
}

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param proot TreeNode类 
     * @param k int整型 
     * @return int整型
     */
    vector<int> res;//用于保存二叉搜索树的节点的值
    void InOrder(TreeNode* proot){
        //中序遍历
        if(proot){
            InOrder(proot->left);
            res.push_back(proot->val);
            InOrder(proot->right);
        }
    }
    int KthNode(TreeNode* proot, int k) {
        // write code here
        if(!proot) return -1;
        InOrder(proot);
        //注意k值不合规的情况
        if(k==0||k>res.size()) return -1;
        else return res[k-1];
    }
};

public class Solution {
    /**
     * 中序遍历 正好是按照BST Node的值 从小到大遍历的。
     * 相当于排序
     */
    int i = 0;
    int res = -1;
    public int KthNode(TreeNode proot, int k) {
        dfs(proot,k);
        return res;
    }
    void dfs(TreeNode proot, int k) {
        if (proot == null)
            return;
        //只有符合条件才继续调用，已经找到第k小，后面就不需要遍历了。
        if (i <= k) {
            dfs(proot.left, k);
             i++;
            if(i==k){
                res=proot.val;
                return;
            }
            dfs(proot.right, k);
        }
    }
}   

/**

• struct TreeNode {

• int val;

• struct TreeNode *left;

• struct TreeNode *right;

• TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

• };

• /
  class Solution {
  public:
  /**

  • 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

  • @param proot TreeNode类

  • @param k int整型

  • @return int整型

  • /
    void dfs(TreeNode* proot, int k, int& sum, int& res)
    {
    if(proot == nullptr) return ;
    dfs(proot->left, k, sum, res);

    sum ++;
    if(sum == k) res = proot->val;

    dfs(proot->right, k, sum, res);
    return ;

    }
    int KthNode(TreeNode* proot, int k) {
    int sum =0 ;
    int res;
    dfs(proot, k, sum, res);
    if(sum < k || sum == 0 || k==0) return -1;
    return res;
    // write code here
    }
    };

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param proot TreeNode类 
     * @param k int整型 
     * @return int整型
     */
    int KthNode(TreeNode* proot, int k) {
        // 时间复杂度O(N)，空间复杂度O(N)
        dfs(proot, k);
        return k == 0 || k > res.size() ? -1 : res[k - 1];
    }
    void dfs(TreeNode *proot, int k) {
        if (proot == nullptr) return;
        dfs(proot->left, k);
        res.push_back(proot->val);  // 中序遍历
        dfs(proot->right, k);
    }
    vector<int> res;
};

public int KthNode (TreeNode proot, int k) {
        // write code here
        if (proot == null || k == 0)return -1;
        num = k;
        return dfs(proot);
    }

    int num = -1;

    int dfs(TreeNode p) {
        int res = -1;
        if (p.left != null)res = dfs(p.left);
        if (res != -1)return res;
        if (num == 1)return p.val;
        num--;
        if (p.right != null)res = dfs(p.right);
        return res;
    }

#include <vector>
class Solution {
public:
    void inorder(TreeNode* proot,vector<int>&ans){
        if(proot==nullptr){
            return;
        }
        inorder(proot->left, ans);
        ans.push_back(proot->val);
        inorder(proot->right,ans);
    }
    int KthNode(TreeNode* proot, int k) {
    if(proot==nullptr||k==0){
        return -1;
    }
    vector<int>ans;
    inorder(proot,ans);
    if(k>ans.size()){
        return -1;
    }
    return ans[k-1];
    }
};

class Solution:
    def KthNode(self , proot: TreeNode, k: int) -> int:
        # write code here
        res = []
        def inorder(root):
            if not root:
                return
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)
        inorder(proot)
        if k > len(res)&nbs***bsp;k <= 0:
            return -1
        return res[k-1]

int cnt;
public int KthNode (TreeNode proot, int k) {
    // write code here
    cnt=k;
    return dfs(proot);

}

public int dfs(TreeNode root){
    if(root==null){
        return -1;
    }
    int left = dfs(root.left);
    if(--cnt==0){
        return root.val;
    }
    int right=dfs(root.right);
    return Math.max(left ,right);
}