- 浏览: 136987 次
文章分类
- 全部博客 (189)
- Tree (14)
- Dynamic Programming (34)
- Array (20)
- Search (1)
- Hash (12)
- Backtracking (22)
- Divide and Conque (8)
- Greedy (6)
- Stack (12)
- software (0)
- List (7)
- Math (22)
- Two pointers (16)
- String (20)
- Linux (1)
- Sliding Window (4)
- Finite State Machine (1)
- Breadth-first Search (7)
- Graph (4)
- DFS (6)
- BFS (3)
- Sort (9)
- 基础概念 (2)
- 沟通表达 (0)
- Heap (2)
- Binary Search (15)
- 小结 (1)
- Bit Manipulation (8)
- Union Find (4)
- Topological Sort (1)
- PriorityQueue (1)
- Design Pattern (1)
- Design (1)
- Iterator (1)
- Queue (1)
最新评论
-
likesky3:
看了数据结构书得知并不是迭代和递归的区别,yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3:
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008:
还有一种find写法:int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008:
要看懂这些技巧的代码确实比较困难。我是这么看懂的:1. 明白这 ...
Leetcode - Single Num II -
qb_2008:
public int singleNumber2(int[] ...
Leetcode - Single Num II
Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.
Note:
Given target value is a floating point.
You may assume k is always valid, that is: k ≤ total nodes.
You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?
[分析]
参考https://leetcode.com/discuss/55240/ac-clean-java-solution-using-two-stacks
中序遍历结果是将树中元素从小到大排列,逆式的中序遍历即先遍历右子树再访问根节点最后遍历左子树会得到树中元素从大到小排列的结果,因此可通过中序遍历获取最接近target节点的perdecessors,通过逆中序遍历获取最接近target节点的successors,然后merge perdecessors 和 successors 获取最接近target节点的 k个节点值。
注意到在中序遍历时遇到比target 大的节点即停止,因为由BST的性质可知后面的元素均会比target 大,即所有target的predecessors均已找到,同理逆中序遍历时遇到不大于 target的节点即可停止递归。
Note:
Given target value is a floating point.
You may assume k is always valid, that is: k ≤ total nodes.
You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?
[分析]
参考https://leetcode.com/discuss/55240/ac-clean-java-solution-using-two-stacks
中序遍历结果是将树中元素从小到大排列,逆式的中序遍历即先遍历右子树再访问根节点最后遍历左子树会得到树中元素从大到小排列的结果,因此可通过中序遍历获取最接近target节点的perdecessors,通过逆中序遍历获取最接近target节点的successors,然后merge perdecessors 和 successors 获取最接近target节点的 k个节点值。
注意到在中序遍历时遇到比target 大的节点即停止,因为由BST的性质可知后面的元素均会比target 大,即所有target的predecessors均已找到,同理逆中序遍历时遇到不大于 target的节点即可停止递归。
/** * 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) { List<Integer> result = new ArrayList<Integer>(); LinkedList<Integer> stackPre = new LinkedList<Integer>(); LinkedList<Integer> stackSucc = new LinkedList<Integer>(); inorder(root, target, false, stackPre); inorder(root, target, true, stackSucc); while (k-- > 0) { if (stackPre.isEmpty()) { result.add(stackSucc.pop()); } else if (stackSucc.isEmpty()) { result.add(stackPre.pop()); } else if (Math.abs(stackPre.peek() - target) < Math.abs(stackSucc.peek() - target)) { result.add(stackPre.pop()); } else { result.add(stackSucc.pop()); } } return result; } public void inorder(TreeNode root, double target, boolean reverse, LinkedList<Integer> stack) { if (root == null) return; inorder(reverse ? root.right : root.left, target, reverse, stack); if ((reverse && root.val <= target) || (!reverse && root.val > target)) return; stack.push(root.val); inorder(reverse ? root.left : root.right, target, reverse, stack); } }
发表评论
-
Inorder Successor in BST
2015-09-26 17:49 718[分析] 参考https://leetcode.com/dis ... -
Lowest Common Ancestor of A Binary Tree
2015-09-26 11:39 567[分析] 最近公共祖先(LCA)是一个经典问题,以前没有好好 ... -
Leetcode - Closest Binary Search Tree Value II
2015-09-13 14:16 785[分析] 思路1:遍历所有节点找到和 target最接近的 k ... -
Leetcode - Graph Valid Tree
2015-09-02 08:50 2269Given n nodes labeled from 0 to ... -
Leetcode - Binary Tree Postorder
2015-08-29 21:07 538[分析] 迭代实现后序遍历比迭代实现先序和中序都要稍微复杂,对 ... -
Leetcode - Binary Tree Upside Down
2015-08-29 18:50 412Given a binary tree where all t ... -
Leetcode - Verify Preorder Sequence in Binary Search Tree
2015-08-29 16:46 3029[分析] 思路1:暴力法,遍历当前待检查数组,找到第一个大于数 ... -
Leetcode - Min Stack
2015-08-29 11:20 551[分析] 这题属于简单题 ... -
Leetcode - Basic Calculator II
2015-08-27 09:16 904mplement a basic calculator to ... -
Leetcode - Converted Sorted List to BST
2015-08-23 20:07 360Given a singly linked list wher ... -
Leetcode - Kth Smallest Element in BST
2015-08-11 10:26 656[分析] 思路1: 递归中序遍历,返回中序遍历中的第k个数。 ... -
Leetcode - Recover Binary Search Tree
2015-07-02 09:27 525Two elements of a binary search ... -
Leetcode - Validate Binary Search Tree
2015-07-01 08:31 594Given a binary tree, determine ... -
Leetcode - Simplify Path
2015-06-17 21:58 423Given an absolute path for a fi ... -
Leetcode - Calculator
2015-06-10 09:31 546[分析] 思路1:逆序遍历字符串,数字和右括号保存在一个堆栈s ... -
Leetcode - Count Complete Tree Nodes
2015-06-07 20:51 772Definition of a complete binary ... -
Leetcode - Contains Duplicate III
2015-06-07 20:08 508Given an array of integers, fi ... -
Leetcode - Maximal Square
2015-06-04 08:25 617Given a 2D binary matrix fille ... -
Leetcode - Maximum Rectangle
2015-05-20 08:58 495Given a 2D binary matrix fill ... -
Leetcode - Largest Rectangle in Histogram
2015-05-20 07:53 491Given n non-negative integers ...
相关推荐
java java_leetcode-99-recover-binary-search-tree
java java_leetcode-107-binary-tree-level-order-traversal
java java_leetcode-102-binary-tree-level-order-traversal
java java_leetcode-110-balanced-binary-tree
java java_leetcode-maximum-depth-of-binary-tree
java java_leetcode-114-flatten-binary-tree-to-linked-list
java java_leetcode-111-minimum-depth-of-binary-tree
java java_leetcode-105-construct-binary-tree-from-preorder-and-inorde
python python_leetcode题解之Binary Search Tree to Greater Sum Tree.py
python python_leetcode_109_Convert_Sorted_List_to_Binary_Search_Tree
java java_leetcode-113-path-sumII
java java_leetcode-101-symmetric-tree
java java_leetcode-100-same-tree
js js_leetcode题解之99-recover-binary-search-tree.js
js js_leetcode题解之98-validate-binary-search-tree.js
java java_leetcode题解之Binary Index Tree Template.java
javascript js_leetcode题解之109-convert-sorted-list-to-binary-search-tree.js
js js_leetcode题解之108-convert-sorted-array-to-binary-search-tree.js
c语言入门 c语言_leetcode题解543-diameter-of-binary-tree.c
js js_leetcode题解之107-binary-tree-level-order-traversal-ii.js