JZ54二叉搜索樹的第k個節點
題目
給定一棵結點數為n 二叉搜索樹，請找出其中的第 k 小的TreeNode結點值，
- 回傳第k小的節點值即可
- 不能查找的情況，如二叉樹為空，則回傳-1，或者k大于n等等，也回傳-1
- 保證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.uj5u.com/houduan/540575.html
標籤：Java