JZ54二叉搜索樹的第k個節點

題目

給定一棵結點數為n 二叉搜索樹，請找出其中的第 k 小的TreeNode結點值。

1. 返回第k小的節點值即可
2. 不能查找的情況，如二叉樹為空，則返回-1，或者k大於n等等，也返回-1
3. 保證n個節點的值不一樣

思路

演算法實現

根據二叉搜索樹的性質，左子樹的元素都小於根節點，右子樹的元素都大於根節點。因此它的中序遍歷（左中右）序列正好是由小到大的次序，
因此我們可以嘗試遞歸中序遍歷，也就是從最小的一個節點開始，找到k個就是我們要找的目標。

具體做法：
step 1：設置全局變數count記錄遍歷了多少個節點，res記錄第k個節點。
step 2：另寫一函數進行遞歸中序遍歷，當節點為空或者超過k時，結束遞歸，返回。
step 3：優先訪問左子樹，再訪問根節點，訪問時統計數字，等於k則找到。
step 4：最後訪問右子樹。

代碼

package mid.JZ54二叉搜索樹的第k個節點;

import java.util.*;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    /**
     * 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可
     *
     * @param proot TreeNode類
     * @param k     int整型
     * @return int整型
     */
    public int KthNode(TreeNode proot, int k) {
        midOrder(proot, k);
        if (res != null) {
            return res.val;
        } else {
            return -1;
        }
    }
public int KthNode2(TreeNode proot, int k) {
        // write code here
        if(proot == null || k == 0) return -1;
        List<Integer> res = new ArrayList<>();
        def(proot, res);
        System.out.println(res.size());
        System.out.println(k);
        System.out.println(res.size()< k);
        if(res.size()< k) return -1;
        Collections.sort(res);
        return res.get(k-1);
}

    public void def(TreeNode proot, List<Integer> res) {
        if (proot == null) return;
        def(proot.left, res);
        res.add(proot.val);
        def(proot.right, res);
    }
    //記錄返回的節點
    private TreeNode res = null;
    //記錄中序遍歷了多少個
    private int count = 0;
    public void midOrder(TreeNode root, int k) {
        if (root == null || count > k) return;

        midOrder(root.left, k);
        count++;
        if (count == k) {
            res = root;
        }
        midOrder(root.right, k);
    }
}