LeetCode 144. Binary Tree Preorder Traversal-二叉树的前序遍历（JAVA迭代及递归方法实现）

题目解读

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

For example:
Given binary tree [1,null,2,3],

   1
    \
     2
    /
   3

return [1,2,3].

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

题意：给一个二叉树，返回其前序遍历的结果。题目中提示，递归方法是微不足道的，可以使用迭代方法。

思路分析

前序遍历，访问顺序是 根节点->左孩子->右孩子。递归方法比较容易实现，具体思路见下面代码；迭代算法实现的主要思路如下：

• 首先判断是否为空树，是，则直接返回；不是，继续；
• 新建一个Stack栈存放未处理的树节点，将根节点压人栈；
• 当栈不为空时，循环执行以下操作：

将当前栈中存放的节点值添加到结果链表中；

判断当前节点是否存在右子树，有则入栈；

判断当前节点是否存在左子树，有则入栈；

（注：这里先push右孩子，再push左孩子，因为栈是先进后出的，左孩子后进，先出，才满足先序遍历的访问顺序 根-左-右。）

• 最后将结果链表返回。

如果一个树如下结果：

按上面的思路，访问二叉树及中间的存储状态如下，最终返回的结果链表顺序是：1、2、4、5、3、6。

代码实现

• 递归实现

/**
     * 递归实现
     * 根据先序遍历的特点，根->左->右
     * @param root
     * @return
     */
    public List<Integer> preorderTraversalRecursive(TreeNode root) {
        List<Integer> list = new ArrayList<>();

        //判断是否为空树
        if (root == null) {
            return list;
        }

        list.add(root.val); //【根】
        list.addAll(preorderTraversalRecursive(root.left)); //【左】通过addAll方法，将根节点的左子树，按preorderTraversalRecursive(root.left)返回的顺序，添加到列表尾部
        list.addAll(preorderTraversalRecursive(root.right));//【右】通过addAll方法，将根节点的右子树，按preorderTraversalRecursive(root.right)返回的顺序，添加到列表尾部

        return list;
    }

• 迭代实现

/**
     * 二叉树的前序遍历
     * 非递归实现（迭代），借助堆栈实现
     * 时间/空间复杂度O(n)
     * @param root
     * @return
     */
    public List<Integer> preorderTraversalInteration(TreeNode root) {
        List<Integer> result = new ArrayList<>(); //存放遍历之后的结果
        Stack<TreeNode> stack = new Stack<>(); //存放未处理的节点

        //判断是否为空树
        if (root == null) {
            return result;
        }

        stack.push(root); //将树根节点压入栈
        while (! stack.isEmpty()){
            TreeNode cur = stack.pop(); //指向当前节点
            result.add(cur.val); //当前节点值添加到结果链表中

            /**
             * 判断当前节点是否存在右子树，有则入栈
             * 判断当前节点是否存在左子树，有则入栈
             * 这里先push右孩子，再push左孩子，因为栈是先进后出的，左后进，先出，才满足先序遍历
             */

            if (cur.right != null) {
                stack.push(cur.right);
            }

            if (cur.left != null) {
                stack.push(cur.left);
            }
        }

        return result;
    }

恶补知识

（1）二叉树的前序遍历，访问顺序 根->左->右

（2）Stack类表示后进先出（LIFO）的对象堆栈，通过五个操作对类Vector进行了扩展，允许将向量是为堆栈。

·isEmpty()：测试此向量是否不包含组件

·pop()：移除堆栈顶部的对象，并最为此函数的值返回对象

·push(E item)：把项压人堆栈顶部

（3）List中的方法

·add(E e)：向列表的尾部添加指定的元素

·addAll(Collection<? extends E> c)：添加制定collection中的所有元素到列表的结尾，顺序是指定collection的迭代器返回这些元素的顺序（可选操作）

（4）迭代与递归的区别

·迭代：循环结构，例如for，while循环，一般是x(n+1)，x(n)之间的关系，x(n+1)=f(x(n))

·递归：递归是迭代的特例，自身调用自身的迭代。例如if else调用自己，并在合适时机退出。经典的斐波那契数列，Fn = Fn-1 + Fn-2。

                                     分割线                                           

小知识大道理，一点一滴积累。给点个赞吧

（个人微信公众号：TestOnTheRoad，搜索ID或者扫描下方二维码添加关注，关注测试开发工程师的成长之路）