剑指offer JZ54 二叉搜索树的第k个节点

描述：

给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。

1.返回第k小的节点值即可

2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1

3.保证n个节点的值不一样

如输入{5,3,7,2,4,6,8},3时，二叉树{5,3,7,2,4,6,8}如下图所示：

该二叉树所有节点按结点值升序排列后可得[2,3,4,5,6,7,8]，所以第3个结点的结点值为4，故返回对应结点值为4的结点即可。

思路：

       首先明确，二叉搜索树，也叫二叉排序树，即左子树的节点的值全都小于根节点，右子树的节点值全都大于根节点，每颗子树也都遵从这个规则。那么很明显，根据这个特性，这棵树经过中序遍历得到的一定是个升序序列。那么问题就很简单了：要找第k小的节点，就是找经过中序遍历后的序列的第k个位置的节点。

代码实现：

public class Solution {
    
    public int KthNode (TreeNode proot, int k) {
        if (proot == null) return -1;

        List<Integer> list = new ArrayList<>();
        MidSearch(proot,list);

        if (k > list.size()) return -1;

        for (int i=0;i<=list.size();++i){
            if (i == k-1) {
                return list.get(i);
            }
        }
        return -1;
    }

    //中序遍历，得到有序序列
    public void MidSearch(TreeNode proot, List<Integer> list){
        if (proot == null) return;
        MidSearch(proot.left,list);
        list.add(proot.val);
        MidSearch(proot.right,list);
    }
}

思考：

        网站上标的难度为中等难度，但其实着重考察的是对二叉搜索树，这种数据结构特性掌握的情况，其中用到了中序遍历，其他的像先序遍历、后续遍历都是需要掌握的，对应于不同的情况。

原文地址：https://blog.csdn.net/main_double/article/details/142417097

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！