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);
    }
}

来源：https://www.cnblogs.com/loongnuts/p/17000104.html
本站部分图文来源于网络，如有侵权请联系删除。