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

谁借莪１个温暖的怀抱￠ 2024-03-16 23:50 24阅读 0赞

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

### 题目 ###

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

**示例 1：**

![317f736f8e66066a644a9e710f2a3ab3.png][]

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

**示例 2：**

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

**示例 3：**

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

**示例 4：**

![ebad3c045896de4a5964ef0dd0cb193b.png][]

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

**示例 5：**  
![c5997ab1af55b9a158c8e0cf5de8f96d.png][]

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

**提示：**

*  树中节点数目在范围  \[ 0 , 100 \] \[0, 100\] \[0,100\] 内
 *   − 100 < = N o d e . v a l < = 100 -100 <= Node.val <= 100 −100<=Node.val<=100

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

--------------------

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

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

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

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

##### 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
    }

##### 复杂度分析 #####

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

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

--------------------

### 迭代解法 ###

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

以 **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;            
    }

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

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

![d78b6ec47386e2b38647ffdf285ca093.png][]

一直将栈中的元素全部取完完事。

##### 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
    }

##### 复杂度分析 #####

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

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

[317f736f8e66066a644a9e710f2a3ab3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/c7aa031154024714a5b44dbcdca447d7.png
[ebad3c045896de4a5964ef0dd0cb193b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/ed0599cee416402f81fb981358116978.png
[c5997ab1af55b9a158c8e0cf5de8f96d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/5a0884c160c24fe8ab1eb0d460918aaf.png
[180b1bd9c039c487213ed4d1f6c925c1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/71e45625baf74b02b5823efe29061508.png
[d78b6ec47386e2b38647ffdf285ca093.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/ce54f062bcf84ed6b5ecce1e575b6aed.png