国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

LeetCode 272 Closest Binary Tree Traversal II 解題思路

Youngdze / 2257人閱讀

摘要:原題網(wǎng)址題意在二叉搜索樹(shù)當(dāng)中找到離最近的個(gè)數(shù)。解題思路由于二叉搜索數(shù)的中序遍歷是有序的,比如例子中的樹(shù),中序遍歷為。

原題網(wǎng)址: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.

題意:在二叉搜索樹(shù)當(dāng)中找到離target最近的K個(gè)數(shù)。

解題思路:
由于二叉搜索數(shù)的inorder中序遍歷是有序的,比如例子中的樹(shù),中序遍歷為[1,2,3,4,5]。我們可以利用這一特性,初始化一個(gè)雙端隊(duì)列Deque,用來(lái)存放k個(gè)數(shù),然后用遞歸的方式,先走到the most left(也就是例子中的1),不斷的向Deque中加入元素,直到元素裝滿,也就是Deque的size()到k個(gè)了,將當(dāng)前元素與target的距離和隊(duì)列頭部與target的距離進(jìn)行對(duì)比,如果當(dāng)前元素的距離更小,則用Deque的pollFirst()方法將頭部吐出,把當(dāng)前元素從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 {
    /**
     *直接在中序遍歷的過(guò)程中完成比較,當(dāng)遍歷到一個(gè)節(jié)點(diǎn)時(shí),
     如果此時(shí)結(jié)果數(shù)組不到k個(gè),我們直接將此節(jié)點(diǎn)值加入res中,
     如果該節(jié)點(diǎn)值和目標(biāo)值的差值的絕對(duì)值小于res的首元素和目標(biāo)值差值的絕對(duì)值,
     說(shuō)明當(dāng)前值更靠近目標(biāo)值,則將首元素刪除,末尾加上當(dāng)前節(jié)點(diǎn)值,
     反之的話說(shuō)明當(dāng)前值比res中所有的值都更偏離目標(biāo)值,
     由于中序遍歷的特性,之后的值會(huì)更加的遍歷,所以此時(shí)直接返回最終結(jié)果即可,
     */
    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的寫(xiě)法,也有必要掌握,必須把控Stack是否為空的情況,當(dāng)前的node為null,但是stack中仍然有元素,依然需要進(jìn)行比較。

/**
 * 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;
    }
    
}

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/71729.html

相關(guān)文章

  • 272. Closest Binary Search Tree Value II

    摘要:題目鏈接的值大小順序?qū)嶋H上就是滿足的條件,所以直接中序遍歷,過(guò)程中維護(hù)一個(gè),放入個(gè)當(dāng)前離最近的值,的時(shí),新的值和的距離如果小于隊(duì)首的那個(gè)值和的距離那么移除隊(duì)首,如果,且新的距離大于等于隊(duì)首的距離,直接退出,返回隊(duì)列中的所有結(jié)果。 272. Closest Binary Search Tree Value II 題目鏈接:https://leetcode.com/problems... ...

    NusterCache 評(píng)論0 收藏0
  • LeetCode 攻略 - 2019 年 7 月下半月匯總(100 題攻略)

    摘要:月下半旬攻略道題,目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題,所以后面會(huì)調(diào)整自己,在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí),攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題,目前已攻略 100 題。 一 目錄 不折騰的前端,和咸魚(yú)有什么區(qū)別...

    tain335 評(píng)論0 收藏0
  • LeetCode 攻略 - 2019 年 7 月上半月匯總(55 題攻略)

    摘要:微信公眾號(hào)記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(jù)題解以及留言內(nèi)容,進(jìn)行補(bǔ)充,并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...

    warmcheng 評(píng)論0 收藏0
  • LeetCode 297. Serialize and Deserialize Binary Tre

    摘要:題目大意將二叉樹(shù)序列化,返回序列化的,和反序列化還原。解題思路技巧在于將記錄為便于將來(lái)判斷。的思想將每一層記錄下來(lái),反序列化時(shí)也按照層級(jí)遍歷的方法依次設(shè)置為上一個(gè)里面的元素的左孩子和右孩子。變種,可以要求輸出一個(gè),而不是 LeetCode 297. Serialize and Deserialize Binary Tree 題目大意: 將二叉樹(shù)序列化,返回序列化的String,和反序列...

    cc17 評(píng)論0 收藏0
  • [Leetcode] Binary Tree Traversal 二叉樹(shù)遍歷

    摘要:棧迭代復(fù)雜度時(shí)間空間遞歸棧空間對(duì)于二叉樹(shù)思路用迭代法做深度優(yōu)先搜索的技巧就是使用一個(gè)顯式聲明的存儲(chǔ)遍歷到節(jié)點(diǎn),替代遞歸中的進(jìn)程棧,實(shí)際上空間復(fù)雜度還是一樣的。對(duì)于先序遍歷,我們出棧頂節(jié)點(diǎn),記錄它的值,然后將它的左右子節(jié)點(diǎn)入棧,以此類推。 Binary Tree Preorder Traversal Given a binary tree, return the preorder tr...

    RaoMeng 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<