二叉树的中序遍历
1.题目内容
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
1
2
| 输入：root = [1,null,2,3]
输出：[1,3,2]
|
示例 2：
示例 3：
提示：
- 树中节点数目在范围
[0, 100] 内
-100 <= Node.val <= 100
2.解法
（1）递归
思路及算法
递归遍历过程如下：
- 前序遍历：打印 - 左 - 右
- 中序遍历：左 - 打印 - 右
- 后序遍历：左 - 右 - 打印
题目要求的是中序遍历，那就按照 左-打印-右这种顺序遍历树就可以了，递归函数实现
- 终止条件：当前节点为空时
- 函数内：递归的调用左节点，打印当前节点，再递归调用右节点
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| //Java
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
dfs(res,root);
return res;
}
void dfs(List<Integer> res, TreeNode root) {
if(root==null) {
return;
}
//按照 左-打印-右的方式遍历
dfs(res,root.left);
res.add(root.val);
dfs(res,root.right);
}
}
|
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(h)，h 是树的高度。
（2）迭代
思路及算法
递归实现时，是函数自己调用自己，一层层的嵌套下去，操作系统/虚拟机自动帮我们用 栈 来保存了每个调用的函数，现在我们需要自己模拟这样的调用过程。
递归的调用过程是不断往左边走，当左边走不下去了，就打印节点，并转向右边，然后右边继续这个过程。
我们在迭代实现时，就可以用栈来模拟上面的调用过程。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| //Java
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
while(stack.size()>0 || root!=null) {
//不断往左子树方向走，每走一次就将当前节点保存到栈中
//这是模拟递归的调用
if(root!=null) {
stack.add(root);
root = root.left;
//当前节点为空，说明左边走到头了，从栈中弹出节点并保存
//然后转向右边节点，继续上面整个过程
} else {
TreeNode tmp = stack.pop();
res.add(tmp.val);
root = tmp.right;
}
}
return res;
}
}
|
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(h)，h 是树的高度