美文网首页
107 Binary Tree Level Order Trav

107 Binary Tree Level Order Trav

作者: yangminz | 来源:发表于2018-07-27 21:12 被阅读6次

    title: Binary Tree Level Order Traversal II
    tags:
    - binary-tree-level-order-traversal-ii
    - No.107
    - simple
    - tree
    - breadth-first-search
    - queue


    Description

    Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

    For example:
    Given binary tree [3,9,20,null,null,15,7],

        3
       / \
      9  20
        /  \
       15   7
    

    return its bottom-up level order traversal as:

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

    Corner Cases

    • empty root

    Solutions

    Queue

    Insert in head for the returned list. Use number counter to divide the layers. It's obvious that the running time is O(V) when the queue operations are all in O(1).

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            Queue<TreeNode>     que  = new LinkedList<TreeNode>();
            List<List<Integer>> llst = new LinkedList<List<Integer>>();
            
            if (root == null) {return llst;}
            que.offer(root);
            int curr = 0;
            int nlay = 1;
    
            while (!que.isEmpty()) {
                nlay = que.size();
                curr = 0;
                List<Integer> a = new LinkedList<Integer>();
                while(curr < nlay) {
                    TreeNode x = que.poll();
                    if (x.left  != null) {que.offer(x.left);}
                    if (x.right != null) {que.offer(x.right);}
                    a.add(x.val);
                    curr = curr + 1;
                }
                llst.add(0, a);
            }
            return llst;
        }
    }
    

    相关文章

      网友评论

          本文标题:107 Binary Tree Level Order Trav

          本文链接:https://www.haomeiwen.com/subject/gvxnmftx.html