LeetCode 272 Closest Binary Tree Traversal II 解题思路

Youngdze 发布于2019-08-16 13:26 / 2199人阅读

摘要：原题网址题意在二叉搜索树当中找到离最近的个数。解题思路由于二叉搜索数的中序遍历是有序的，比如例子中的树，中序遍历为。

原题网址：https://leetcode.com/problems...

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)?

Hint:

Consider implement these two helper functions:

getPredecessor(N), which returns the next smaller node to N.
getSuccessor(N), which returns the next larger node to N.

Try to assume that each node has a parent pointer, it makes the problem much easier.

Without parent pointer we just need to keep track of the path from the root to the current node using a stack.

You would need two stacks to track the path in finding predecessor and successor node separately.

题意：在二叉搜索树当中找到离target最近的K个数。

解题思路：
由于二叉搜索数的inorder中序遍历是有序的，比如例子中的树，中序遍历为[1,2,3,4,5]。我们可以利用这一特性，初始化一个双端队列Deque，用来存放k个数，然后用递归的方式，先走到the most left（也就是例子中的1），不断的向Deque中加入元素，直到元素装满，也就是Deque的size()到k个了，将当前元素与target的距离和队列头部与target的距离进行对比，如果当前元素的距离更小，则用Deque的pollFirst()方法将头部吐出，把当前元素从addLast()加入。

Example:

Input: root = [4,2,5,1,3], target = 3.714286, and k = 2

    4
   / 
  2   5
 / 
1   3

Output: [4,3]

代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    /**
     *直接在中序遍历的过程中完成比较，当遍历到一个节点时，
     如果此时结果数组不到k个，我们直接将此节点值加入res中，
     如果该节点值和目标值的差值的绝对值小于res的首元素和目标值差值的绝对值，
     说明当前值更靠近目标值，则将首元素删除，末尾加上当前节点值，
     反之的话说明当前值比res中所有的值都更偏离目标值，
     由于中序遍历的特性，之后的值会更加的遍历，所以此时直接返回最终结果即可，
     */
    public List closestKValues(TreeNode root, double target, int k) {
        Deque deque = new ArrayDeque<>();
        inorder(root, target, k, deque);
        List res = new ArrayList<>(deque);
        return res;
    }
    private void inorder(TreeNode root, 
                         double target, 
                         int k, 
                         Deque deque) {
        if (root == null) return;
        inorder(root.left, target, k, deque);
        if (deque.size() < k) {
            deque.offer(root.val);
        } else if (Math.abs(root.val - target) < Math.abs(deque.peekFirst()-target) ) {
            deque.pollFirst();
            deque.addLast(root.val);
        } 
        inorder(root.right, target, k, deque);
    }
}

还有一种用Stack完成的方式，思路和递归相同，但是iterative的写法，也有必要掌握，必须把控Stack是否为空的情况，当前的node为null，但是stack中仍然有元素，依然需要进行比较。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List closestKValues(TreeNode root, double target, int k) {
        Deque deque = new ArrayDeque<>();
        Stack stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if (deque.size() < k) {
                deque.addLast(cur.val);
            } else if (Math.abs(cur.val - target) < Math.abs(deque.peekFirst() - target)) {
                deque.pollFirst();
                deque.addLast(cur.val);
            }
            cur = cur.right;
        }
        List res = new ArrayList<>(deque);
        return res;
    }
    
}

云服务器 GPU云服务器解题思路 binary-tree binary-search-tree Traversal

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71729.html

272. Closest Binary Search Tree Value II

摘要：题目链接的值大小顺序实际上就是满足的条件，所以直接中序遍历，过程中维护一个，放入个当前离最近的值，的时，新的值和的距离如果小于队首的那个值和的距离那么移除队首，如果，且新的距离大于等于队首的距离，直接退出，返回队列中的所有结果。 272. Closest Binary Search Tree Value II 题目链接：https://leetcode.com/problems... ...

NusterCache 2019-08-14 17:35 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
LeetCode 297. Serialize and Deserialize Binary Tre

摘要：题目大意将二叉树序列化，返回序列化的，和反序列化还原。解题思路技巧在于将记录为便于将来判断。的思想将每一层记录下来，反序列化时也按照层级遍历的方法依次设置为上一个里面的元素的左孩子和右孩子。变种，可以要求输出一个，而不是 LeetCode 297. Serialize and Deserialize Binary Tree 题目大意: 将二叉树序列化，返回序列化的String，和反序列...

cc17 2019-08-16 13:28 评论0 收藏0
[Leetcode] Binary Tree Traversal 二叉树遍历

摘要：栈迭代复杂度时间空间递归栈空间对于二叉树思路用迭代法做深度优先搜索的技巧就是使用一个显式声明的存储遍历到节点，替代递归中的进程栈，实际上空间复杂度还是一样的。对于先序遍历，我们出栈顶节点，记录它的值，然后将它的左右子节点入栈，以此类推。 Binary Tree Preorder Traversal Given a binary tree, return the preorder tr...

RaoMeng 2019-08-14 12:25 评论0 收藏0