解法
中順走査では、各ノードを左・ノード・右の順に訪問します。明示的なスタックには、左部分木の処理がまだ完了していないノードを保存します。ルートから始めて、左へ進めるところまで進みながら各ノードをスタックに積みます。次に、次のノードを取り出して値を結果に追加し、その右の子へ移動します。現在のノードとスタックが両方空になったら走査を終了します。ルートが null の場合も空のリストを返します。
スタックにはルートから葉までの経路だけが入るため、補助領域は木の高さを H として O(H) です。各ノードを一度ずつ積み、取り出すため、時間計算量は O(N) です。この走査は木を読み取るだけで、ノードを変更しません。
Java
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
/**
* 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<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
ArrayDeque<TreeNode> stack = new ArrayDeque<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
result.add(current.val);
current = current.right;
}
return result;
}
}