题目描述

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

解题思路

二叉搜索树-二叉排序树 特点：左<中<右 二叉搜索树中序遍历为从小到大的一组树 即，中序遍历树，每个结点存在ArrayList中，当k>=1并且list.size()>=k，返回list.get(k-1) 否则，返回null

二叉树中序遍历-递归法

/* 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 { List<TreeNode> list = new ArrayList<>(); TreeNode KthNode(TreeNode pRoot, int k) { count(pRoot); if(k>=1 && list.size()>k-1){ return list.get(k-1); } return null; } //中序遍历 public void count(TreeNode p){ if(p!=null) { count(p.left); list.add(p); count(p.right); } } }

二叉树中序遍历-非递归

/* 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) { Stack<TreeNode> stack = new Stack<>();//建立栈 TreeNode p = pRoot; if(pRoot == null || k<1) return null; while(!stack.empty() || p!=null) { if(p!=null){ stack.push(p); p = p.left; } else{ p = stack.pop(); k--; if(k==0){ return p; } p = p.right; } } return null; } /* 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 { List<TreeNode> list = new ArrayList<>(); TreeNode KthNode(TreeNode pRoot, int k) { count(pRoot); if(k>=1 && list.size()>=k){ return list.get(k-1); } return null; } public void count(TreeNode p){ Stack<TreeNode> stack = new Stack<>(); while(!stack.empty() || p!=null) { if(p!=null){ stack.push(p); p = p.left; } else{ p = stack.pop();//注意！！！ list.add(p); p = p.right; } } } }