314. Binary Tree Vertical Order Traversal

anyway 發布于2019-08-14 17:27 / 1635人閱讀

摘要：題目鏈接這道題要求的來保存結果，一開始想到的是用遍歷的時候更新，比如現在的，有左孩子的話就在最前面插入結果，且。不過這樣的話每個的時間是了。還需要遍歷從而得到要求的結果，因為沒有，所以還需要保存下的最小值和最大值，從而知道遍歷的范圍。

314. Binary Tree Vertical Order Traversal

題目鏈接：https://leetcode.com/problems...

這道題要求vertical的order來保存結果，一開始想到的是用遍歷的時候更新index，比如現在的index = 0，有左孩子的話就在最前面插入結果，且shift++。不過這樣的話每個subproblem的時間是O(N)了。
那么可以先用hashmap來cache，遍歷的時候就要根據node所在的column的index來存，根節點的index從0開始，左邊的孩子index-1，右邊的孩子index+1，遍歷樹結束之后可以把所有index已經對應的值保存下來。還需要遍歷hashmap從而得到要求的結果，因為hashmap沒有order，所以還需要保存下index的最小值和最大值，從而知道hashmap遍歷的范圍。第一遍tree的遍歷可以bfs也可以dfs。

public class Solution {
    public List> verticalOrder(TreeNode root) {
        // store the val according to their index in col
        map = new HashMap();
        List> result = new ArrayList();
        if(root == null) return result;
        
        // traverse the tree
        bfs(root);
        // traverse map to get result
        for(int i = low; i <= high; i++) {
            if(map.containsKey(i)) {
                result.add(map.get(i));
            }
        }
        return result;
    }
    
    Map> map;
    int low = 0, high = 0;
    private void bfs(TreeNode root) {
        // bfs, use queue
        Queue q = new LinkedList();
        Queue index = new LinkedList();
        q.offer(root);
        index.offer(0);
        while(!q.isEmpty()) {
            TreeNode cur = q.poll();
            int curIndex = index.poll();
            // add node according to the column index
            if(!map.containsKey(curIndex)) map.put(curIndex, new ArrayList());
            map.get(curIndex).add(cur.val);
            // update lowest index and highes index
            low = Math.min(low, curIndex);
            high = Math.max(high, curIndex);
            
            if(cur.left != null) {
                q.offer(cur.left);
                index.offer(curIndex - 1);
            }
            if(cur.right != null) {
                q.offer(cur.right);
                index.offer(curIndex + 1);
            }
        }
    }
}

云服務器 GPU云服務器 binary-tree binary-search-tree vertical Traversal

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66649.html

[Leetcode] Binary Tree Traversal 二叉樹遍歷

摘要：棧迭代復雜度時間空間遞歸棧空間對于二叉樹思路用迭代法做深度優先搜索的技巧就是使用一個顯式聲明的存儲遍歷到節點，替代遞歸中的進程棧，實際上空間復雜度還是一樣的。對于先序遍歷，我們出棧頂節點，記錄它的值，然后將它的左右子節點入棧，以此類推。 Binary Tree Preorder Traversal Given a binary tree, return the preorder tr...

RaoMeng 2019-08-14 12:25 評論0 收藏0
[Leetcode-Tree]Binary Tree Level Order Traversal

摘要：解題思路層次遍歷二叉樹，我們采用隊列，本題的注意點是需要分割出每一層的序列，所以在從隊列中取元素之前，我們要先記錄隊列的大小，以表示這一層中節點的個數。 Binary Tree Level Order TraversalGiven a binary tree, return the level order traversal of its nodes values. (ie, from...

Half 2019-08-16 10:26 評論0 收藏0
[LeetCode] 429. N-ary Tree Level Order Traversal (

429. N-ary Tree Level Order Traversal Given an n-ary tree, return the level order traversal of its nodes values. (ie, from left to right, level by level). For example, given a 3-ary tree:showImg(https...

LiangJ 2019-08-19 11:18 評論0 收藏0
leetcode102. Binary Tree Level Order Traversal

摘要：題目要求對于一棵樹進行序遍歷。水平遍歷即遍歷結束當前行以后再遍歷下一行，并將每行的結果按行填入到數組中返回。利用水平遍歷的話，我們只需要知道當前元素在樹中的高度就可以知道應當插入到那個數組中。題目要求 Given a binary tree, return the level order traversal of its nodes values. (ie, from left to...

Coding01 2019-08-16 12:09 評論0 收藏0
leetcode-102-Binary Tree Level Order Traversal

102. 二叉樹的層次遍歷題目描述給定一個二叉樹，返回其按層次遍歷的節點值。（即zhucengde，從左到右訪問）。例如: 給定二叉樹: [3,9,20,null,null,15,7], 3 / 9 20 / 15 7 返回其層次遍歷結果為： [ [3], [9,20], [15,7] ] class Solution: def le...

widuu 2019-07-31 11:07 評論0 收藏0