当前位置:网站首页>剑指offer之打印二叉搜索树中第k小的结点

剑指offer之打印二叉搜索树中第k小的结点

2020-11-09 22:41:03 龙韬

题目概述

给定一棵二叉搜索树,请找出其中的第k小的结点。

解题思路

一开始我没有注意到二叉搜索树这个词,我还是以为是一个普通的二叉树,所以我就按照我的想法,将二叉树的节点放入到一个数组中。

我的解题的思路

由于一开始我没有注意到二叉搜索树这个概念,所以的我的思路是按照普通二叉树的查找进行的,具体思路如下所示:

  1. 首先判断当前节点是否为空,k是否小于0.如果为真,则返回的是null
  2. 新建一个长度为k个数组,这个数组中将按照Node的val进行排序,排序函数为moveArr
  3. moveArr函数中定义了将节点按照直接插入排序的思想进行排序。
  4. 然后递归的将二叉树的节点依次放入到数组中,返回数组中的最后一个元素即为第k小的元素

官方给的题解

当我完成我的算法并且通过的时候,我再一次查看题解时发现,我还是粗心了,并没有发现题目中所给出的隐含的意思。二叉搜索树是一个非常特别的二叉树,当一个节点的左子树和右子树都存在时,左子树中的值都小于该节点,右子树中的所有值都大于该节点。
二叉搜索树的中序遍历就是一个升序排序的数组,所以查找第k小的节点,就查找数组中索引为k-1的节点即可。
但是中序遍历是找到所有的节点,但是我们只需要找到第k小的节点即可,所以我们对算法有了一些改进,使用非递归的中序遍历,找到第k小的节点就跳出循环。

具体的思路:

  1. 首先判断当前节点是否为空,k是否小于0.如果为真,则返回的是null
  2. 将新建一个Stack栈,用来存放中序遍历过程中的节点。
  3. 将执行while循环直到节点为null与stack为空时才停止。
  • 在循环过程中,判断节点是否为空,如果不为空,则将该节点加入到栈中,并且将指针指向节点的左子节点;
  • 如果为空则将node指向栈抛出的节点上,然后计数器++;判断是否找到第k个元素,如果找到则返回,如果没有则将节点指针指向当前节点的右子节点。

代码的实现

树节点的函数:

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

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

    }

使用数组存储的方式

 TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot == null || k < 1) return null;
        // 看到这个问题,我首先想到的方法是,将树放入到一个数组中,然后将数组进行判断,返现最小的数值
        // 首先新建一个k位大小的数组,然后依次遍历二叉树,将数值插入到该数组中
        TreeNode[] arr = new TreeNode[k];
        addTreeNode(pRoot, arr);
        return arr[k-1];
    }
    
    // 遍历将数节点加入到数组中
    public void addTreeNode(TreeNode node, TreeNode[] arr){
        if(node == null) return;
        moveArr(node, arr);
        if(node.left != null) addTreeNode(node.left, arr);
        if(node.right != null) addTreeNode(node.right, arr);
    }
    
    // 数组移位, 判断数组要比哪一个小
    public void moveArr(TreeNode node, TreeNode[] arr){
        if(node == null) return;
        for(int i=0; i<arr.length; i++){
            if(arr[i] == null){
                arr[i] = node;
                return;
            }else if(node.val < arr[i].val){
                for(int j = arr.length-1; j > i; j--){
                    arr[j] = arr[j-1];
                }
                arr[i] = node;
                return;
            }
        }
    }

使用中序遍历查找的方法

 TreeNode KthNode(TreeNode pRoot, int k){
         // 一开始没有仔细的看待问题,如果仔细的看问题以及对二叉树非常熟悉的话,应该第一时间就注意到了 二叉搜索树 这个词语
         // ,二叉搜索树中一个节点的左子树中的值应该小于该节点,右子树中的值都应该大于该节点
         if(pRoot == null || k < 1) return null;
         // 二叉树的中序遍历就可以找到该节点的排序,只要找到第k个元素就可以找到问题中所要找的节点
         // 非递归的方法需要使用Stack来存储父节点
         TreeNode node = pRoot;
         Stack<TreeNode> stack = new Stack<>();
         int count = 0;
         while(node != null || !stack.isEmpty()){
             if(node != null){
                 stack.push(node);
                 node = node.left;
             }else{
                 node = stack.pop();
                 count ++;
                 if(count == k) return node;
                 node = node.right;
             }
         }
         return null;
         
     }

版权声明
本文为[龙韬]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/liulongtao/p/13951337.html