题目

给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：给定二叉树 [3,9,20,null,null,15,7],

 3 / \ 9 20 / \ 15 7

返回其自底向上的层次遍历为：

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

题解

利用层次遍历,层次遍历的时候进入下一层的时候记录一下当前队列中有几个元素。

class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> levelVal = new LinkedList<>(); while (size > 0) { TreeNode current = queue.poll(); if (current.left != null) { queue.add(current.left); } if (current.right != null) { queue.add(current.right); } levelVal.add(current.val); size--; } res.add(0, levelVal); } return res; } }

用递归去做。用递归去做的关键在于需要把层数也带上。

class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } helper(root, res, 0); return res; } public void helper(TreeNode root, List<List<Integer>> res, int depth) { if (root == null) { return; } if (depth == res.size()) { res.add(0, new LinkedList<>()); } List<Integer> current = res.get(res.size() - depth - 1); helper(root.left, res, depth + 1); helper(root.right, res, depth + 1); current.add(root.val); } }

热门阅读

Leetcode 名企之路 手撕代码 QQ 群：805423079，群密码：1024

3 条回复

snowonion

2019-03-15 11:01:18 +08:00

https://www.codewars.com/kata/sort-binary-tree-by-levels 的 Haskell 解法的高票答案，稍加修改就能用在这里。

（剧透警告）

注意这里二叉树的定义方式是

```haskell
data TreeNode a = TreeNode {
left :: Maybe (TreeNode a),
right :: Maybe (TreeNode a),
value :: a
} deriving Show
```

解答:

```haskell
levelOrderBottomUpHierarchical :: Maybe (TreeNode a) -> [[a]]
levelOrderBottomUpHierarchical = reverse . takeWhile (not . null) . go
where
go Nothing = repeat []
go (Just x) = [value x] : zipWith (++) (go $ left x) (go $ right x)
```

测试：

```haskell
leaf v = Just (TreeNode {left = Nothing, right = Nothing, value = v})

t3 = Just (TreeNode {
left = leaf 9,
right = Just (TreeNode {
left = leaf 15,
right = leaf 7,
value = 20
}),
value = 3
})

-- ghci 执行
-- > levelOrderBottomUpHierarchical t3
-- [[15,7],[9,20],[3]]
```

snowonion

2019-03-15 11:03:13 +08:00

@snowonion #1
缩进没了？！ wtf

msg7086

2019-03-15 11:07:28 +08:00

@snowonion 要贴 Markdown 需要开主题。

[Leetcode] 107. 二叉树的层次遍历 II

题目

题解

热门阅读