二叉樹層序周遊

給你一個二叉樹，請你傳回其按 層序周遊 得到的節點值。 （即逐層地，從左到右通路所有節點）。

示例：

二叉樹：[3,9,20,null,null,15,7]

3
 / \
9  20
  /  \
 15   7
           

傳回其層序周遊結果：

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        
    }
}
           

解法

遞歸

package com.javaedge.middle.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author apple
 */
public class BinaryTreeLevelOrderTraversal {

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    private static List<List<Integer>> levels = new ArrayList<>();

    public static void helper(TreeNode node, int level) {
        // 假設将 root 作為第 0 層
        if (levels.size() == level) {
            // 可得，此時需要新增該層級
            levels.add(new ArrayList<>());
        }
        // 對應層級的節點值list
        levels.get(level).add(node.val);

        // 遞歸周遊左子樹
        if (node.left != null) {
            helper(node.left, level + 1);
        }
        // 遞歸周遊右子樹
        if (node.right != null) {
            helper(node.right, level + 1);
        }
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return levels;
        }
        helper(root, 0);
        return levels;
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(3);
        TreeNode node2 = new TreeNode(9);
        TreeNode node3 = new TreeNode(20);
        TreeNode node4 = new TreeNode(15);
        TreeNode node5 = new TreeNode(7);
        node1.left = node2;
        node1.right = node3;
        node3.left = node4;
        node3.right = node5;
        System.out.println(levelOrder(node1));
    }
}