314. Binary Tree Vertical Order Traversal

anyway 发布于2019-08-14 17:27 / 1446人阅读

摘要：题目链接这道题要求的来保存结果，一开始想到的是用遍历的时候更新，比如现在的，有左孩子的话就在最前面插入结果，且。不过这样的话每个的时间是了。还需要遍历从而得到要求的结果，因为没有，所以还需要保存下的最小值和最大值，从而知道遍历的范围。

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);
            }
        }
    }
}

私有云海外云主机 binary-tree binary-search-tree vertical Traversal

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

转载请注明本文地址：https://www.ucloud.cn/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