V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Acceml
V2EX  ›  程序员

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

  •  
  •   Acceml ·
    Acceml · 2019-03-15 08:51:04 +08:00 · 1729 次点击
    这是一个创建于 2062 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

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

    例如: 给定二叉树 [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

    snowonion
        1
    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
        2
    snowonion  
       2019-03-15 11:03:13 +08:00
    @snowonion #1
    缩进没了?! wtf
    msg7086
        3
    msg7086  
       2019-03-15 11:07:28 +08:00   ❤️ 1
    @snowonion 要贴 Markdown 需要开主题。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3310 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 00:04 · PVG 08:04 · LAX 16:04 · JFK 19:04
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.