【力扣每日一题】144. 二叉树的前序遍历

待我称王封你为后i 2022-12-18 15:58 128阅读 0赞

# 1. 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center]

# 2. 题目解析 #

*  非常典型的一道二叉树题目
 *  思路一：[递归求解][Link 1]
 *  思路二：[迭代求解][Link 1]

# 3. 题目代码 #

## 3.1 递归 ##

**public IList<int> PreorderTraversal(TreeNode root)
            {
        
                List<int> list = new List<int>();
                Tree(root, list);
                return list;
            }
    
            public static void Tree(TreeNode root, List<int> list)
            {
        
                if(root != null)
                {
        
                    list.Add(root.val);
                    Tree(root.left, list);
                    Tree(root.right, list);
                }
            }**

## 3.2 迭代 ##

public IList<int> PreorderTraversal(TreeNode root)
            {
        
                Stack<TreeNode> stack = new Stack<TreeNode>();
                IList<int> list = new List<int>();
                if (root != null)
                {
        
                    stack.Push(root);
                }
                while (stack.Count != 0)
                {
        
                    TreeNode temp = stack.Peek();
                    stack.Pop();
                    if (temp != null)
                    {
        
                        if (temp.right != null)
                        {
        
                            stack.Push(temp.right);
                        }
                        if(temp.left != null)
                        {
        
                            stack.Push(temp.left);
                        }
                        stack.Push(temp);
                        stack.Push(null);
                    }
                    else
                    {
        
                        list.Add(stack.Peek().val);
                        stack.Pop();
                    }
                }
    
                return list;
            }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/621c0b7c65254ea8b4a4c7e035c5124d.png
[Link 1]: https://blog.csdn.net/qq_40915439/article/details/107749015