Algorithm

94.binary-tree-inorder-traversal

Description:

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

1
2
3
4
5
6
7
8
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

說明：

1
2
3
4
5
    4
   / \
  2   6
 / \ / \
1  3 5  7
遍歷方式 輸出結果 搜尋演算法
Pre-Order Traversal 4213657 Depth-first Search
In-Order Traversal 1234567 Depth-first Search
Post-Order Traversal 1325764 Depth-first Search
Level-Order Traversal 4261357 Breadth-first Search

Pre-, In-, Post- 是指parent node相對於child node的順序。
而Level-則是依照層級關係。

First Answer (Recursive):

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
<?php

namespace LeetCode\BinaryTreeInorderTraversal;

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

    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    public function inorderTraversal($root)
    {
        $this->findAnswer($root);
        return $this->answer;
    }

    /**
     * @param TreeNode $root
     */
    private function findAnswer($root)
    {
        /**
         * 先把左子樹找完
         */
        if (!is_null($root->left)) {
            $this->findAnswer($root->left);
        }

        /**
         * 沒有左子樹後，填入根（自己）
         */
        $this->answer[] = $root->val;

        /**
         * 再找右子樹
         */
        if (!is_null($root->right)) {
            $this->findAnswer($root->right);
        }
    }
}
  • Time Complexity: O(n)

Other Answer (Iterating + Stack):

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
<?php

namespace LeetCode\BinaryTreeInorderTraversal;

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

    /**
     * @var Integer[]
     */
    protected $stack = [];

    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    public function inorderTraversal($root)
    {
        $this->findAnswer($root);
        return $this->answer;
    }

    /**
     * @param TreeNode $root
     */
    private function findAnswer($root)
    {
        while (count($this->stack) > 0 || !is_null($root)) {
            if (!is_null($root)) {
                $this->stack[] = $root;
                $root = $root->left;
            } else {
                $pop = array_pop($this->stack);
                $this->answer[] = $pop->val;

                if (!is_null($pop->right)) {
                    $root = $pop->right;
                }
            }
        }
    }
}
  • Time Complexity: O(n)

ʕ •ᴥ•ʔ：還有看到一種Morris Traversal的方法，之後遇到再補充。