剑指offer62 二叉搜索树的第k个结点

剑指offer62

二叉搜索树的第k个结点

题目描述

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

示例

输入

{5,3,7,2,4,6,8},3

输出

{4}

思路

二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。

所以，按照中序遍历顺序找到第k个结点就是结果。

代码1：递归

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

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

    }

}
*/

public class Solution {
    int index = 0;
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot!=null){
            TreeNode node = KthNode(pRoot.left,k);
            if(node!=null)return node;
            index++;
            if(index==k)return pRoot;
            node = KthNode(pRoot.right,k);
            if(node!=null)return node;
        }
        return null;
    }
}

/**
思路：
//二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。
//所以，按照中序遍历顺序找到第k个结点就是结果。
*/

上述代码首先执行 Kt(5,3),Kt(3,3),Kt(2,3),Kt(null,3),此时pRoot=null，执行return null, 返回到调用处TreeNode node = KthNode(pRoot.left,k)，此时，pRoot=2,

然后顺序执行，if(node!=null) return node index=1, 然后执行2的右结点Kt(null,3)，结点为null，执行return null， 返回node = KthNode(pRoot.right,k)，此时，pRoot=null，顺序执行return null，返回TreeNode node = KthNode(pRoot.left,k)，此时，pRoot=3， node=null，注意 这里的 return null 执行了两次！ 第一次返回右结点调用处，第二次返回左结点调用处。

顺序执行 index=2，node = KthNode(pRoot.right,k)即Kt(4,3)，然后执行TreeNode node = KthNode(pRoot.left,k)，… ，最终执行到

if(index==k)return pRoot;
node = KthNode(pRoot.right,k);
if(node!=null)return node;
TreeNode node = KthNode(pRoot.left,k);

然后，将 pRoot=4 返回。

代码2：利用栈

此外，可考虑用栈实现遍历：

https://blog.csdn.net/sunshineoe/article/details/109899318

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
import java.util.*;
//使用的栈进行遍历
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k)
    {
      //计数器，记录的是第count小的元素
          int count = 0;
          if(pRoot == null || k <= 0){
              return null;
          }
          // 定义栈进行存储数据
          Stack<TreeNode> stack = new Stack<>();
          TreeNode node = pRoot;
          // 栈不空，结点不为空
          while(!stack.isEmpty() || node != null){
              // 如果结点不为空，
              if(node != null){
                  //将当前结点的左子树结点入栈
                  stack.push(node);
                  //结点继续移动到左边的子结点
                  node = node.left;
              }else{
                /**
                  当前结点不为空的时候，当点结点出栈，
                  判断出栈后的元素是否有右结点，有右节点指向右节点
                  结点不为空的话进栈，类似的步骤
                */
                // 出栈弹出的元素，就是按照从小到大的顺序输出的最小值。
                node = stack.pop();
                // 每弹出一个元素，计数器计数一次
                count++;
                // 计数器的大小等于K的时候，返回第k小的元素
                if(count == k){
                  return node;
                }
                node = node.right;
              }
          }
      return null;
    }
}

附：二叉搜索树实现

https://www.cnblogs.com/yahuian/p/10813614.html

以下程序可供调试，查看递归算法的流程(需在maven项目中引入test依赖)

import org.junit.jupiter.api.Test;

public class BinarySearchTree
{ // 二叉搜索树类
    private class TreeNode
    { // 节点类
        int data; // 数据域
        TreeNode right; // 右子树
        TreeNode left; // 左子树
    }

    private TreeNode root; // 树根节点

    public void insert(int key)
    {
        TreeNode p=new TreeNode(); //待插入的节点
        p.data=key;

        if(root==null)
        {
            root=p;
        }
        else
        {
            TreeNode parent;
            TreeNode current=root;
            while(true)
            {
                parent=current;
                if(key>current.data)
                {
                    current=current.right; // 右子树
                    if(current==null)
                    {
                        parent.right=p;
                        return;
                    }
                }
                else //本程序没有做key出现相等情况的处理，暂且假设用户插入的节点值都不同
                {
                    current=current.left; // 左子树
                    if(current==null)
                    {
                        parent.left=p;
                        return;
                    }
                }
            }
        }
    }


    @Test
    public void test(){
        BinarySearchTree tree=new BinarySearchTree();

        tree.insert(5);
        tree.insert(3);
        tree.insert(7);
        tree.insert(2);
        tree.insert(4);
        tree.insert(6);
        tree.insert(8);


        System.out.println(KthNode(tree.root,3));

    }


    int index = 0;
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot!=null){
            TreeNode node = KthNode(pRoot.left,k);
            if(node!=null)return node;
            index++;
            if(index==k)return pRoot;
            node = KthNode(pRoot.right,k);
            if(node!=null)return node;
        }
        return null;
    }
}