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

1. 题目描述

2. 题目解析

• 非常典型的一道二叉树题目
• 思路一：递归求解
• 思路二：迭代求解

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