1. 问题描述
Given a binary tree, return the inorder traversal of its nodes' values.
Example:
Input: [1,null,2,3] 1 2 / 3
Output: [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively?
翻译过来就是实现二叉树的中序遍历。
2. 思路
- 使用非递归的思路
- 定义一个栈用于存储节点
- 若当前节点不为空，当前节点入栈，持续将左孩子入栈
- 从栈里pop出一个节点 root，这个节点就是最左边的节点。
- 把root节点的值放入返回的list中
- 然后将root指向这个节点的右孩子
3. 代码
代码语言：javascript复制/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (true) {
if(root != null) {
stack.push(root);
root = root.left;
} else {
if (stack.isEmpty()) {
break;
}
root = stack.pop();
result.add(root.val);
root = root.right;
}
}
return result;
}
}
