144.二叉树的前序遍历

LeetCode LeetCode 树 深度优先搜索 二叉树 栈
发布时间 :
字数:1.6k 阅读 : 评论:
  1. 144.二叉树的前序遍历
    1. 144.1 题目
    2. 144.2 题解
      1. 递归法前序遍历二叉树
      2. 迭代法前序遍历二叉树
    3. 144.3 代码
    4. 144.4 运行结果

144.二叉树的前序遍历

144.1 题目

给你二叉树的根节点 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]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶：

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

144.2 题解

递归法前序遍历二叉树

// 方法一：递归法前序遍历二叉树
// 判断节点为不为空加到结果列表中，递归左右子树
static List<int> PreorderTraversal1(TreeNode root)
{
    // 创建一个列表，用于存储前序遍历结果
    List<int> result = new List<int>();

    // 调用递归方法进行前序遍历
    PreorderTraversalRecursive(root, result);

    // 返回最终结果
    return result;
}

// 递归方法，用于前序遍历二叉树
static void PreorderTraversalRecursive(TreeNode node, List<int> result)
{
    // 如果节点不为空
    if (node != null)
    {
        // 将节点值加入结果列表
        result.Add(node.val);

        // 递归遍历左子树
        if (node.left != null)
        {
            PreorderTraversalRecursive(node.left, result);
        }

        // 递归遍历右子树
        if (node.right != null)
        {
            PreorderTraversalRecursive(node.right, result);
        }
    }
}

迭代法前序遍历二叉树

// 方法二：迭代法前序遍历二叉树
// 将每一层的节点逐个压入栈中（前序遍历先压右子树再压左子树），弹出节点加到结果列表在压入弹出节点的右左子树
static List<int> PreorderTraversal2(TreeNode root)
{
    // 创建一个列表，用于存储前序遍历结果
    List<int> result = new List<int>();

    // 如果根节点为空，直接返回空列表
    if (root == null)
    {
        return result;
    }

    // 创建一个栈，用于迭代遍历二叉树
    Stack<TreeNode> stack = new Stack<TreeNode>();
    // 将根节点压入栈
    stack.Push(root);

    // 迭代遍历
    while (stack.Count > 0)
    {
        // 弹出栈顶节点
        TreeNode node = stack.Pop();
        // 将节点值加入结果列表
        result.Add(node.val);

        // 由于栈是先进后出，所以先将右子树压入栈
        if (node.right != null)
        {
            stack.Push(node.right);
        }

        // 再将左子树压入栈
        if (node.left != null)
        {
            stack.Push(node.left);
        }
    }

    // 返回最终结果
    return result;
}

144.3 代码

using System;
using System.Collections.Generic;

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int x)
    {
        val = x;
    }
}

class Program
{
    static void Main()
    {
        #region 题目

        // 给你二叉树的根节点 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]

        // 提示：
        // 树中节点数目在范围 [0, 100] 内
        // -100 <= Node.val <= 100

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

        #endregion

        #region 测试

        // 示例 1
        TreeNode root1 = new TreeNode(1)
        {
            right = new TreeNode(2)
            {
                left = new TreeNode(3)
            }
        };
        List<int> result1 = PreorderTraversal1(root1);
        Console.WriteLine($"示例1 方法1 输出：{string.Join(", ", result1)}");
        List<int> result1_2 = PreorderTraversal2(root1);
        Console.WriteLine($"示例1 方法2 输出：{string.Join(", ", result1_2)}");

        // 示例 2
        TreeNode root2 = null;
        List<int> result2 = PreorderTraversal1(root2);
        Console.WriteLine($"示例2 方法1 输出：{string.Join(", ", result2)}");
        List<int> result2_2 = PreorderTraversal2(root2);
        Console.WriteLine($"示例2 方法2 输出：{string.Join(", ", result2_2)}");

        // 示例 3
        TreeNode root3 = new TreeNode(1);
        List<int> result3 = PreorderTraversal1(root3);
        Console.WriteLine($"示例3 方法1 输出：{string.Join(", ", result3)}");
        List<int> result3_2 = PreorderTraversal2(root3);
        Console.WriteLine($"示例3 方法2 输出：{string.Join(", ", result3_2)}");

        // 示例 4
        TreeNode root4 = new TreeNode(1)
        {
            right = new TreeNode(2)
        };
        List<int> result4 = PreorderTraversal1(root4);
        Console.WriteLine($"示例4 方法1 输出：{string.Join(", ", result4)}");
        List<int> result4_2 = PreorderTraversal2(root4);
        Console.WriteLine($"示例4 方法2 输出：{string.Join(", ", result4_2)}");

        // 示例 5
        TreeNode root5 = new TreeNode(1)
        {
            right = new TreeNode(2)
        };
        List<int> result5 = PreorderTraversal1(root5);
        Console.WriteLine($"示例5 方法1 输出：{string.Join(", ", result5)}");
        List<int> result5_2 = PreorderTraversal2(root5);
        Console.WriteLine($"示例5 方法2 输出：{string.Join(", ", result5_2)}");

        #endregion
    }

    #region 答案

    // 方法一：递归法前序遍历二叉树
    // 判断节点为不为空加到结果列表中，递归左右子树
    static List<int> PreorderTraversal1(TreeNode root)
    {
        // 创建一个列表，用于存储前序遍历结果
        List<int> result = new List<int>();

        // 调用递归方法进行前序遍历
        PreorderTraversalRecursive(root, result);

        // 返回最终结果
        return result;
    }

    // 递归方法，用于前序遍历二叉树
    static void PreorderTraversalRecursive(TreeNode node, List<int> result)
    {
        // 如果节点不为空
        if (node != null)
        {
            // 将节点值加入结果列表
            result.Add(node.val);

            // 递归遍历左子树
            if (node.left != null)
            {
                PreorderTraversalRecursive(node.left, result);
            }

            // 递归遍历右子树
            if (node.right != null)
            {
                PreorderTraversalRecursive(node.right, result);
            }
        }
    }

    // 方法二：迭代法前序遍历二叉树
    // 将每一层的节点逐个压入栈中（前序遍历先压右子树再压左子树），弹出节点加到结果列表在压入弹出节点的右左子树
    static List<int> PreorderTraversal2(TreeNode root)
    {
        // 创建一个列表，用于存储前序遍历结果
        List<int> result = new List<int>();

        // 如果根节点为空，直接返回空列表
        if (root == null)
        {
            return result;
        }

        // 创建一个栈，用于迭代遍历二叉树
        Stack<TreeNode> stack = new Stack<TreeNode>();
        // 将根节点压入栈
        stack.Push(root);

        // 迭代遍历
        while (stack.Count > 0)
        {
            // 弹出栈顶节点
            TreeNode node = stack.Pop();
            // 将节点值加入结果列表
            result.Add(node.val);

            // 由于栈是先进后出，所以先将右子树压入栈
            if (node.right != null)
            {
                stack.Push(node.right);
            }

            // 再将左子树压入栈
            if (node.left != null)
            {
                stack.Push(node.left);
            }
        }

        // 返回最终结果
        return result;
    }

    #endregion
}

144.4 运行结果

示例1 方法1 输出：1, 2, 3
示例1 方法2 输出：1, 2, 3
示例2 方法1 输出：
示例2 方法2 输出：
示例3 方法1 输出：1
示例3 方法2 输出：1
示例4 方法1 输出：1, 2
示例4 方法2 输出：1, 2
示例5 方法1 输出：1, 2
示例5 方法2 输出：1, 2
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏