LeetCode之二叉树非递归前序遍历

问题描述：

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:
Given binary tree{1,#,2,3},

   1
    \
     2
    /
   3

return[1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

使用非递归的方法前序遍历二叉树。

问题分析

前序遍历就是按照中、左、右的顺序对二叉树进行遍历。

思路很简单，如果当前节点不为空，不断遍历当前节点的左子树，如果当前节点有右子树的话，将其放入栈中以便后期遍历其右子树，如果当前节点为空，则取出栈顶元素按照同样的方式遍历其右子树。

代码实现

package com.postorder.raversal;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @author [email protected]
 * @since 2018/11/17 下午3:16
 */
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。