My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
Stack<TreeNode> st = new Stack<TreeNode>();
Stack<TreeNode> pre = new Stack<TreeNode>();
Stack<TreeNode> suc = new Stack<TreeNode>();
TreeNode p = root;
while (p != null) {
st.push(p);
p = p.left;
}
while (!st.isEmpty()) {
p = st.pop();
if (p.val > target) {
break;
}
pre.push(p);
if (p.right != null) {
p = p.right;
while (p != null) {
st.push(p);
p = p.left;
}
}
}
st.clear();
p = root;
while (p != null) {
st.push(p);
p = p.right;
}
while (!st.isEmpty()) {
p = st.pop();
if (p.val <= target) {
break;
}
suc.push(p);
if (p.left != null) {
p = p.left;
while (p != null) {
st.push(p);
p = p.right;
}
}
}
List<Integer> ret = new ArrayList<Integer>();
while (k > 0) {
if (pre.isEmpty()) {
ret.add(suc.pop().val);
}
else if (suc.isEmpty()) {
ret.add(pre.pop().val);
}
else if (Math.abs(pre.peek().val - target) < Math.abs(suc.peek().val - target)) {
ret.add(pre.pop().val);
}
else {
ret.add(suc.pop().val);
}
k--;
}
return ret;
}
}
reference:
https://discuss.leetcode.com/topic/22940/ac-clean-java-solution-using-two-stacks/2
沒能自己做出來荸频×庑ぃ看了解析,覺得思路是那么的理所當(dāng)然旭从,竟然沒想出來稳强。场仲。。
他給的答案是recursion
我重寫了一個(gè) iteration的方法退疫,都差不多渠缕。
一個(gè)注意點(diǎn)是,
如果 pre 的break條件是 val > target
那么 suc 的break條件必須是 val <= target
不能是 val < target
否則褒繁,會(huì)把相同的數(shù)字放進(jìn)兩個(gè)棧中亦鳞,造成錯(cuò)誤的結(jié)果。
以后再給你一個(gè)binary search tree,的確可以用這種雙棧的辦法棒坏,實(shí)現(xiàn)雙指針燕差,從中間往左右掃描。
Anyway, Good luck, Richardo! -- 09/07/2016