【算法题解】42. 二叉树的前序遍历

❝

这是一道 「简单」 题
https://leetcode.cn/problems/binary-tree-preorder-traversal/

❞

题目

给你二叉树的根节点 root ，返回它节点值的 「前序」 遍历。

示例 1：

输入：root = [1,null,2,3] 
输出：[1,2,3]

示例 2：

输入：root = [] 
输出：[]

示例 3：

输入：root = [1] 
输出：[1]

示例 4：

输入：root = [1,2] 
输出：[1,2]

示例 5：

输入：root = [1,null,2] 
输出：[1,2]

提示：

树中节点数目在范围内

进阶：递归算法很简单，你可以通过迭代算法完成吗？

递归解法（深度优先搜索）

「前序遍历」：即最先遍历根节点，顺序为 「根节点 -> 左子树 -> 右子树」。

其中左子树和右子树的遍历同样遵循前序遍历的规则。

前序遍历，也就是我们常说的「深度优先遍历（或深度优先搜索）」，是典型的递归算法的运用。

Java 代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        dfs(root, ans);
        return ans;
    }


    private void dfs(TreeNode node, List<Integer> ans){
        if(node == null){
            return;
        }
        ans.add(node.val);
        dfs(node.left, ans);
        dfs(node.right, ans);
    }  
}

Go 代码实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) (ans []int) {
    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode){
        if node == nil {
            return
        }
        ans = append(ans, node.Val)
        dfs(node.Left)
        dfs(node.Right)
    }

    dfs(root)

    return ans
}

复杂度分析

时间复杂度：，N 为二叉树中节点的个数，每个节点都需要遍历一次，总计 N 次。

空间复杂度：，N 为二叉树中节点的个数，空间复杂度取决于递归调用栈的深度，最多为 N, 即二叉树退化成链表的时候。

迭代解法

首先将当前节点的值放入答案数组中，然后找到当前节点的左节点并将其值放入答案，一路向下逐层找左节点，直到最后一个节点没有左节点为止（如下图中的节点3）。

以 Java 为例，假如 ans 表示答案，那么此刻的代码应该是这样子的：

 while(root != null){
    ans.add(root.val);
    root = root.left;            
}

节点3 遍历完后，按照规则，我们接下来应该要找到 节点4，要找到节点4 就必须通过 节点2 才行。

通过 节点3 倒退到 节点2，刚好符合栈的特性，「后进先出」，节点3 出来后接着就是 节点2。

上面在找左节点的 while 循环修改为：

 while(root != null){
    ans.add(root.val);
    stack.push(root);
    root = root.left;            
}

当左节点遍历完后，出栈栈顶元素，看其是否有右节点：

没有(如节点3)：就不做任何处理，然后继续出栈下一个栈顶元素。
有(如节点2)：找到其右节点，然后对这个右节点再执行一次上面的那个 while 循环，因为这个右节点的前序遍历和根结点的前序是一样的逻辑。

以此类推，一直将栈中的元素全部取完为止。

Java 代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        while(root != null){
            ans.add(root.val);
            stack.push(root);
            root = root.left;            
        }
        while(!stack.isEmpty()){
            TreeNode top = stack.pop();
            root = top.right;
            while(root != null){
                ans.add(root.val);
                stack.push(root);
                root = root.left;            
            }
        }

        return ans;
    } 
}

Go 代码实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) (ans []int) {
    stack := []*TreeNode{}

    for root != nil {
        ans = append(ans, root.Val)
        stack = append(stack, root)
        root = root.Left
    }

    for len(stack) > 0 {
        top := stack[len(stack) - 1]
        stack = stack[0:len(stack) - 1]
        root = top.Right
        for root != nil {
            ans = append(ans, root.Val)
            stack = append(stack, root)
            root = root.Left
        }
    }

    return ans
}