卖萌的弱渣

I am stupid, I am hungry.

Binary Tree Level Order Traversal II

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],

1
2
3
4
5

3
   / \
  9  20
/  \
   15   7

return its bottom-up level order traversal as:

1
2
3
4
5

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

Solution

  • BFS 然后翻转结果
(Binary-Tree-Level-Order-Traversal2.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """

        stack = [root]
        ret = []

        if not root:
            return ret

        while stack:
            new_stack = []
            ret.append([n.val for n in stack])
            for node in stack:
                if node.left:
                    new_stack.append(node.left)
                if node.right:
                    new_stack.append(node.right)
            stack = new_stack
        return list(reversed(ret))
  • java solution: BFS, 需要stack辅助
(Binary-Tree-Level-Order-Traversal2.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> ret = new LinkedList<List<Integer>>();
        if (root == null)
            return ret;

        // queue add
        queue.offer(root);

        while (!queue.isEmpty()){
            List<Integer> list = new LinkedList<Integer>();
            // 一层多少点
            int levelNums = queue.size();
            for (int i = 0;i<levelNums;i++){
                TreeNode top = queue.element();
                if (top.left != null)
                    queue.offer(top.left);
                if (top.right != null)
                    queue.offer(top.right);
                list.add(top.val);
                // 把点删掉
                queue.poll();
            }
            ret.add(0,list);
        }
        return ret;
    }

}