1 题目

二叉树的前序遍历

2 解

2.1 我的解

由于他要对每一层进行分层,所以我想的就是通过 List<List<TreeNode>> 去分层,但是我这个解跑出来的效果看上去时间复杂度和空间复杂度都不好,无语。

 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
40
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        List<List<TreeNode>> nodeList = new ArrayList<>();
        if (root == null) return result;
        result.add(new ArrayList(){{add(root.val);}});
        nodeList.add(new ArrayList(){{add(root);}});
        nodeList.add(new ArrayList(){{
            if (root.left != null) add(root.left); 
            if (root.right != null) add(root.right);
        }});
        recursive(result, nodeList, 1);
        return result;
    }
    
    private void recursive(List<List<Integer>> result, 
                           List<List<TreeNode>> nodeList, int layer){
        if (layer + 1> nodeList.size()) return;
        List<TreeNode> subNodeList = nodeList.get(layer);
        List<Integer> numList = new ArrayList<>();
        List<TreeNode> nextLayerNodeList = new ArrayList<>();
        for (TreeNode node : subNodeList) {
            numList.add(node.val);
            if (node.left != null) nextLayerNodeList.add(node.left);
            if (node.right != null) nextLayerNodeList.add(node.right);
        }
        if (numList.size() > 0) result.add(numList);
        if (nextLayerNodeList.size() > 0) nodeList.add(nextLayerNodeList);
        recursive(result, nodeList, layer + 1);
    }
}

2.2 递归解法

在递归的时候传递层数,所以根据层数能拿到 list,递归遍历一遍就搞定了

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

     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
    
    /**
    * Definition for a binary tree node.
    * public class TreeNode {
    *     int val;
    *     TreeNode left;
    *     TreeNode right;
    *     TreeNode(int x) { val = x; }
    * }
    */
    class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        recursive(result, root, 1);
        return result;
    }
        
    private void recursive(List<List<Integer>> result, TreeNode root, int layer) {
        if (root == null) return;
        if (layer > result.size()) {
            result.add(new ArrayList<Integer>());
        }
        List<Integer> currentLayerList = result.get(layer - 1);
        currentLayerList.add(root.val);
        recursive(result, root.left, layer + 1);
        recursive(result, root.right, layer + 1);
    }
    }