每天进步一点点🤏

二叉树的中序遍历

  • ~2.01K 字

二叉树的中序遍历

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

解法

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
思路:
二叉树的中序遍历为左中右,前序遍历为中左右,后序遍历为左右中
将二叉树的节点以右中左的顺序循环写入数组,使用array_pop获取节点,
如果获取的节点是左右节点,则继续写入数组,否则返回节点的值

代码:
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;
    }
}

/**
 * inorderTraversal
 *
 * @param TreeNode $root
 *
 * @return array
 */
function inorderTraversal(TreeNode $root)
{
    $res   = [];
    $stack = [];
    $this->push($stack, $root);

    while (!empty($stack)) {
        //写入的顺序是右中左,array_pop拿到的顺序就是左中右
        $s    = array_pop($stack);
        $node = $s['node'];

        //如果获取的节点是值节点,将节点的值写入数组
        if ($s['type'] === 'value') {
            $res[] = $node->val;
            continue;
        }

        //如果获取的节点是左右节点,写入数组
        $this->push($stack, $node);
    }

    return $res;
}

/**
 * push 以右中左的顺序写入数组中
 *
 * @param               $stack
 * @param TreeNode|null $node
 *
 * @return void
 */
private function push(&$stack, TreeNode $node = null)
{
    // 中序遍历的顺序是 左中右 反过来是右中左
    // 前序遍历的顺序是 中左右 反过来是右左中
    // 后序遍历的顺序是 左右中 反过来是中右左
    // 只需要改变写入顺序就可以实现这三种遍历
    if ($node->right) {
        $stack[] = [
            'type' => 'node',
            'node' => $node->right,
        ];
    }

    $stack[] = [
        'type' => 'value',
        'node' => $node,
    ];

    if ($node->left) {
        $stack[] = [
            'type' => 'node',
            'node' => $node->left,
        ];
    }
}