94. 二叉树的中序遍历

题目描述

原题
给定一个二叉树,返回它的中序 遍历。
示例:
1
输入: [1,null,2,3]
2
1
3
\
4
2
5
/
6
3
7
8
输出: [1,3,2]
Copied!
进阶: 递归算法很简单,你可以通过迭代算法完成吗?

题解

递归

1
class Solution {
2
public List<Integer> inorderTraversal(TreeNode root) {
3
List<Integer> list = new ArrayList<>();
4
if(root != null){
5
list.addAll(inorderTraversal(root.left));
6
list.add(root.val);
7
list.addAll(inorderTraversal(root.right));
8
}
9
return list;
10
}
11
}
Copied!

迭代

1
class Solution {
2
public List<Integer> inorderTraversal(TreeNode root) {
3
List<Integer> list = new ArrayList<>();
4
LinkedList<TreeNode> stack = new LinkedList<>();
5
while(!stack.isEmpty()||root!=null){
6
//循环将左子树都添加到栈内
7
//弹出最后一个左子树
8
//将这个左子树的值添加到list中,
9
//如果这个左子树右子树不为空,则添加到栈中
10
//重复上述操作
11
while(root!=null){
12
stack.push(root);
13
root = root.left;
14
}
15
TreeNode node = stack.pop();
16
list.add(node.val);
17
root = node.right;
18
}
19
return list;
20
}
21
}
Copied!
最近更新 6mo ago