題目描述
給定一棵二叉搜索樹，請找出其中的第k小的結點，例如， （5，3，7，2，4，6，8） 中，按結點數值大小順序第三小結點的值為4，
思路
非遞回中序遍歷二叉樹的應用，時間復雜度O(lgn)，空間復雜度O(lgn)，
代碼
import java.util.LinkedList;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
TreeNode KthNode(TreeNode pRoot, int k)
{
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode curr = pRoot;
int index = 0;
while(!stack.isEmpty() || curr != null) {
while(curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
index++;
if(index == k) {
return curr;
} else {
curr = curr.right;
}
}
return null;
}
}
筆記
無
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/57192.html
標籤：其他
上一篇：序列化二叉樹
下一篇：對圖片中值模糊運算出錯的問題