Leetcode-144-二叉树的前序遍历

Leecode-144 Binary Tree Preorder Traversal

思路：递归/迭代

题目描述

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

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

输出: [1,2,3]

Solution：

• 前序遍历
  • 根
  • 左孩子
  • 右孩子

• 中序遍历
  • 左孩子
  • 根
  • 右孩子

• 后序遍历
  • 左孩子
  • 右孩子
  • 根

Java

Solution :递归

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root,res);
        return res;
    }
    private void helper(TreeNode root, List<Integer> res) {
        // 判断当前是否是null
        if (root != null){
            // 1. 打印
            res.add(root.val);

            // 2. 左子树
            if (root.left != null){
                helper(root.left,res);
            }
            // 3. 右子树
            if (root.right != null){
                helper(root.right,res);
            }
        }
    }

}

• 时间复杂度：如果树是平衡的O(logn) ， 最坏情况O(n)

• 空间复杂度：O(n) 需要一个辅助栈

Solution :迭代

class Solution{
    public List<Integer> preorderTraversal(TreeNode root){
        LinkedList<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> result = new LinkedList<>();

        // 特判
        if (root == null){
            return result;
        }

        // 先加入根节点
        stack.add(root);


        while (!stack.isEmpty()){
            // 处理节点(这里模仿stack一定要删除最后一个元素)
            TreeNode curr = stack.removeLast();
            result.add(curr.val);

            // 处理叶子节点
            // 因为要倒着出栈，先丢右孩子入栈，在丢左孩子入栈
            if (curr.right != null){
                stack.add(curr.right);
            }
            if (curr.left != null){
                stack.add(curr.left);
            }
        }
        return result;
    }
}

• 时间复杂度：访问每个节点恰好一次，时间复杂度为 O(N) ，其中 *N 是节点的个数，也就是树的大小。
• 空间复杂度：取决于树的结构，最坏情况存储整棵树，因此空间复杂度是 O(N)。

Python

Solution :

打赏