题目
给定一个二叉树，返回它的中序 遍历。
示例：
输入: [1,null,2,3]
1
2
/
3
输出: [1,3,2]
解答
第一种、递归遍历
public static List<Integer> inorderTraversal(TreeNode root) {
List<Integer> nodes = new ArrayList<>();
return helper(root, nodes);
}
public static List<Integer> helper(TreeNode treeNode, List<Integer> list) {
if (treeNode != null) {
if (treeNode.left != null){
helper(treeNode.left,list);
}
list.add(treeNode.val);
if (treeNode.right != null){
helper(treeNode.right,list);
}
}
return list;
}
第二种、使用栈的方式
public static List<Integer> inorder(TreeNode treeNode, List<Integer> list) {
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = treeNode;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
list.add(curr.val);
curr = curr.right;
}
return list;
}
解析
1、使用递归的方式简单暴力
2、
- 中序 ：左 -> 根 -> 右
- 前序 ：根 -> 左 -> 右
- 后序 ：左 -> 右 -> 根
遍历树，总是从根开始，而中序需要左，这种结构使用栈的方式存储，右节点依次遍历。
