欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-04-27 11:20:31
...

题目解读

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左孩子,因为栈是先进后出的,左孩子后进,先出,才满足先序遍历的访问顺序 根-左-右。

  • 最后将结果链表返回。

如果一个树如下结果:

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

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

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

代码实现

  • 递归实现
/**
     * 递归实现
     * 根据先序遍历的特点,根->左->右
     * @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。

                                     分割线                                           

小知识大道理,一点一滴积累。给点个赞吧LeetCode 144. Binary Tree Preorder Traversal-二叉树的前序遍历(JAVA迭代及递归方法实现)

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

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