其他
【二叉树打卡3】二叉树的先序遍历（非递归版）
前言
昨天把二叉树的先序遍历和中序遍历的题目给弄错了，今天重新补发下。
【题目】
按照二叉树的先序遍历打印二叉树，并且不能使用递归。
【难度】
易
解答
二叉树的先序遍历顺序是根-左-右。我们可以采用一个栈来辅助，我们把先序遍历的结果放到一个 ArrayList 容器中作为返回值，具体步骤如下：
1、把二叉树的根节点 root 放进栈。
2、如果栈不为空，从栈中取出一个节点，把该节点放入容器的尾部；如果该节点的右子树不为空，则把有节点放入栈；如果该节点的左子树不为空，则把左子树放入栈中。
3、一直重复步骤 2 ，直到栈为空，此时遍历结束，代码如下：
代码如下：
// 迭代版
static List<Integer> preOderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root == null)
return result;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode tmp = stack.pop();
result.add(tmp.val);
if(tmp.right != null)
stack.push(tmp.right);
if(tmp.left != null)
stack.push(tmp.right);
}
return result;
}