Algorithm

107.binary-tree-level-order-traversal-ii

Description:

Given the root of a binary tree, return the bottom-up level order traversal of its nodes’ values. (i.e., from left to right, level by level from leaf to root).

Example:

1
2
3
4
5
6
7
8
Input: root = [3,9,20,null,null,15,7]
        3
      /   \
     9     20
          /  \
        15    7

Output: [[15,7],[9,20],[3]]
1
2
Input: root = [1]
Output: [[1]]
1
2
Input: root = []
Output: []

深度優先搜尋 (Depth-First Search, DFS)
搜尋頂點時，先探查單一路線，直到無法繼續前進，再折返探查下一個選項路徑。
過程中，因展開而得到的頂點選項，可利用堆疊 (Stack) 的資料結構。

廣度優先搜尋 (Breadth-First Search, BFS)
搜尋頂點時，從起點經由邊搜尋頂點，直到找到指定的頂點。
過程中，因展開而得到的頂點選項，可利用佇列 (Queue) 的資料結構。

First Answer (DFS):

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
<?php

namespace LeetCode\BinaryTreeLevelOrderTraversalII;

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution
{
    /**
     * @var array
     */
    protected $answer = [];

    /**
     * @param TreeNode $root
     * @return Integer[][]
     */
    public function levelOrderBottom($root)
    {
        if (is_null($root->val)) {
            return [];
        }

        $this->findAnswer($root);
        $this->reverse();
        return $this->answer;
    }

    /**
     * @param TreeNode $root
     * @param int $level
     */
    private function findAnswer($root, $level = 0)
    {
        if (is_null($root->val)) {
            return;
        }

        $this->answer[$level] = array_merge($this->answer[$level] ?? [], [$root->val]);

        $this->findAnswer($root->left, $level + 1);
        $this->findAnswer($root->right, $level + 1);
    }

    private function reverse()
    {
        $this->answer = array_reverse($this->answer);
    }
}

Other Answer (BFS):

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
<?php

namespace LeetCode\BinaryTreeLevelOrderTraversalII;

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution
{
    /**
     * @var array
     */
    protected $answer = [];

    /**
     * @param TreeNode $root
     * @return Integer[][]
     */
    public function levelOrderBottom($root)
    {
        if (is_null($root->val)) {
            return [];
        }

        $this->answer[0] = [$root->val];
        $this->findAnswer($root);
        $this->reverse();
        return $this->answer;
    }

    /**
     * @param TreeNode $root
     */
    private function findAnswer($root, $level = 1)
    {
        if (is_null($root->val)) {
            return;
        }

        if (!is_null($root->left)) {
            $this->answer[$level] = array_merge($this->answer[$level] ?? [], [$root->left->val]);
        }

        if (!is_null($root->right)) {
            $this->answer[$level] = array_merge($this->answer[$level] ?? [], [$root->right->val]);
        }

        $this->findAnswer($root->left, $level + 1);
        $this->findAnswer($root->right, $level + 1);
    }

    private function reverse()
    {
        $this->answer = array_reverse($this->answer);
    }
}

ʕ •ᴥ•ʔ：欣賞一下 DFS 和 BFS 思考上的不同。