[LintCode/LeetCode] Binary Tree Level Order Traver

makeFoxPlay 发布于2019-08-14 15:48 / 3036人阅读

Problem

Given a binary tree, return the level order traversal of its nodes" values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Note

用先入先出的Queue。用size标记每一层的结点数目并定向循环。

Solution

class Solution {
    public List> levelOrder(TreeNode root) {
        List> res = new ArrayList<>();
        if (root == null) return res;
        Queue queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List temp = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
                temp.add(cur.val);
            }
            res.add(temp);//for traversal II: res.add(0, temp);
        }
        return res;
    }
}

DFS

class Solution {
    public List> levelOrder(TreeNode root) {
        List> res = new ArrayList<>();
        dfs(root, 0, res);
        return res;
    }
    private void dfs(TreeNode root, int level, List> res) {
        if (root == null) return;
        if (level >= res.size()) res.add(new ArrayList()); //level >= res.size() ---- from 0 >= 0 to initialize
        res.get(level).add(root.val);
        dfs(root.left, level+1, res);
        dfs(root.right, level+1, res);
    }
}

From bottom

public class Solution {
    public ArrayList> levelOrderBottom(TreeNode root) {
        ArrayList> res = new ArrayList<>();
        if (root == null) return res;
        helper(root, res, 0);
        return res;
    }
    public void helper(TreeNode root, ArrayList> res, int index) {
        int size = res.size();
        if (index == size) {
            ArrayList curList = new ArrayList<>();
            curList.add(root.val);
            res.add(0, curList);
        }
        else res.get(size-index-1).add(root.val);
        if (root.left != null) helper(root.left, res, index+1);
        if (root.right != null) helper(root.right, res, index+1);
    }
}

GPU云服务器云服务器 binary-tree binary-search-tree Binary level

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

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

[LintCode/LeetCode] Binary Tree Zigzag Level Orde

Problem Given a binary tree, return the zigzag level order traversal of its nodes values. (ie, from left to right, then right to left for the next level and alternate between). Example Given binary tr...

AlphaGooo 2019-08-14 15:40 评论0 收藏0
[LintCode/LeetCode] Construct Binary Tree from Tr

摘要：做了几道二分法的题目练手，发现这道题已经淡忘了，记录一下。这道题目的要点在于找的区间。边界条件需要注意若或数组为空，返回空当前进到超出末位，或超过，返回空每次创建完根节点之后，要将加，才能进行递归。 Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder t...

马忠志 2019-08-14 15:40 评论0 收藏0
[LintCode/LeetCode] Flatten Binary Tree to Linked

Problem Flatten a binary tree to a fake linked list in pre-order traversal.Here we use the right pointer in TreeNode as the next pointer in ListNode. Example 1 1 ...

TNFE 2019-08-14 15:12 评论0 收藏0
[LintCode/LeetCode] Balanced Binary Tree

摘要：根据二叉平衡树的定义，我们先写一个求二叉树最大深度的函数。在主函数中，利用比较左右子树的差值来判断当前结点的平衡性，如果不满足则返回。 Problem Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as...

morgan 2019-08-14 15:33 评论0 收藏0
[LintCode/LeetCode] Binary Tree Pruning

Problem Binary Tree PruningWe are given the head node root of a binary tree, where additionally every nodes value is either a 0 or a 1. Return the same tree where every subtree (of the given tree) not...

rockswang 2019-08-16 12:37 评论0 收藏0