问题描述：
Given a binary tree, return the preorder traversal of its nodes’ values.
For example:
Given binary tree{1,#,2,3},
return[1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
使用非递归的方法前序遍历二叉树。
问题分析
前序遍历就是按照中、左、右的顺序对二叉树进行遍历。
思路很简单，如果当前节点不为空，不断遍历当前节点的左子树，如果当前节点有右子树的话，将其放入栈中以便后期遍历其右子树，如果当前节点为空，则取出栈顶元素按照同样的方式遍历其右子树。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| package com.postorder.raversal;
import java.util.ArrayList;
import java.util.Stack;
public class PreOrderSolution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode pointer = root;
while (pointer != null || !stack.isEmpty()) {
while (pointer != null) {
list.add(pointer.val);
if (pointer.right != null) {
stack.push(pointer);
}
pointer = pointer.left;
}
if (stack.isEmpty()) {
break;
}
pointer = stack.pop();
pointer = pointer.right;
}
return list;
}
}
|
牛客网做得还不错，就是现在还是只支持 C++ 和 Java。