Problem
Solution
Initial thoughts
Python implementation
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
|
class : def levelOrderBottom(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ def dfs(node, depth): if node is None: return if len(self.ans) > depth: self.ans[-1-depth].append(node.val) else: self.ans = [[node.val]]+self.ans dfs(node.left, depth+1) dfs(node.right, depth+1) self.ans = [] dfs(root, 0) return self.ans
|
Java implementation
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
|
* Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class { private List<List<Integer>> ans = new ArrayList<>(); private void dfs(TreeNode node, int depth){ if(node==null){ return ; } if(ans.size() > depth){ ans.get(ans.size()-1-depth).add(node.val); } else{ List<Integer> temp = new ArrayList<>(); temp.add(node.val); ans.add(0, temp); } dfs(node.left, depth+1); dfs(node.right, depth+1); } public List<List<Integer>> levelOrderBottom(TreeNode root) { dfs(root, 0); return ans; } }
|
Time complexity
O(n)
Space complexity
O(n)
Links
107. Binary Tree Level Order Traversal II
(中文版) 算法笔记: 力扣#107 二叉树的层次遍历 II
近期评论