LeetCode：二叉树的前序遍历【144】

题目描述

给定一个二叉树，返回它的前序遍历。

示例:

输入: [1,null,2,3]

   1

    \

     2

    /

   3 

输出: [1,2,3]

题目分析

　　如果用递归代码的话，很简单，先序遍历，就是先遍历当前节点，接着是左孩子然后是右孩子，到每个孩子都是这样的处理过程。

    public void preorder(TreeNode root,List<Integer> res)

    {

        if(root==null)

            return;

        res.add(root.val);

        preorder(root.left,res);

        preorder(root.right,res);

    }

　　但是这道题，我们可以用栈来模拟递归的过程，从而加深对递归的理解程度。随便找一个二叉树，我们来手工模拟一下这个出入栈过程：

　　刚开始的时候1在栈内，也在栈顶。打印完1以后，我们需要把它的两个孩子加入到栈中，此时有一个问题，我们需要先加左还是先加右？

　　我们需要把下一个需要打印的元素发在栈顶，如果先加左孩子的话，那么右孩子就会处于栈顶，此时打印栈顶的话就是右孩子的值3，所以栈要先加右孩子，再加左孩子。

　　所以过程是：【1入栈】、1出栈打印输出1

　　　　　　　　【3入栈、2入栈】，2出栈打印输出2，然后【4入栈】，4出栈打印输出4，3出栈打印输出3.

Java题解

public List<Integer> preorderTraversal(TreeNode root) {

        List<Integer> res = new ArrayList<>();

        if(root==null)

            return res;

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        while (!stack.empty())

        {

            TreeNode node = stack.pop();

            res.add(node.val);

            if(node.right!=null)

                stack.push(node.right);

            if(node.left!=null)

                stack.push(node.left);

        }

        return res;

}

巴特西

LeetCode：二叉树的前序遍历【144】

LeetCode：二叉树的前序遍历【144】

题目描述

题目分析

Java题解

最新文章

热门文章