题目
题目地址:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
给定一个二叉树,返回它的中序
遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
答案
使用栈实现(DFS)
package com.jarome.leetcode.test1.inordertraversal;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
// 中序遍历:左子树 -> 根节点 -> 右子树
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
TreeNode peek = stack.peek();
if (peek.left != null) {
stack.push(peek.left);
peek.left = null;
continue;
}
stack.pop();
res.add(peek.val);
if (peek.right != null) {
stack.push(peek.right);
}
}
return res;
}
}
执行情况:
- 执行用时:1ms
- 内存消耗:38.1MB