144. 二叉树的前序遍历

Bertha 。 2022-12-09 01:59 177阅读 0赞

# 题目： #

[144. 二叉树的前序遍历][144.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]

# 题解： #

**[144. 二叉树的前序遍历][144. 1]  
[94. 二叉树的中序遍历][94.]  
[145. 二叉树的后序遍历][145.]**

## 1. 题解一：递归前序遍历 ##

第一种解决方法是使用递归。这是经典的方法，直截了当。我们可以定义一个辅助函数来实现递归。

## 2. 题解二：迭代前序遍历 ##

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

# 代码： #

## 1. 代码一：递归前序遍历 ##

/** * code144 */
    
    import java.util.*;
    
    public class code144 { 
    
        // 解法一：递归
        public static List<Integer> preorderTraversal(TreeNode root) { 
            List<Integer> res = new ArrayList<>();
            preorder(root, res);
            return res;
        }
    
        public static void preorder(TreeNode root, List<Integer> res) { 
            if (root == null) { 
                return;
            }
            res.add(root.val);
            preorder(root.left, res);
            preorder(root.right, res);
        }
    
        public static void main(String[] args) { 
            // 根据给定的数组创建一棵树
            Integer nums[] = {  1, null, 2, 3 };
            TreeNode tree = ConstructTree.constructTree(nums);
            // 将刚刚创建的树打印出来
            TreeOperation.show(tree);
    
            // Integer nums[] = { 5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1 };
            // TreeNode tree = ConstructTree.constructTree(nums);
            // ConstructTree.preOrder(tree);
            // System.out.println();
            // ConstructTree.midOrder(tree);
            // System.out.println();
            // ConstructTree.aftOrder(tree);
            // System.out.println();
    
            // TreeOperation.show(tree);
    
            System.out.println("前序遍历：");
            List<Integer> list = preorderTraversal(tree);
            for (int i = 0; i < list.size(); i++) { 
                System.out.print(list.get(i) + " ");
            }
            System.out.println();
        }
    }

## 2. 代码二：迭代前序遍历 ##

/** * code144 */
    
    import java.util.*;
    
    public class code144 { 
    
        // 解法二：迭代
        public static List<Integer> preorderTraversal(TreeNode root) { 
            List<Integer> res = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            while (cur != null || !stack.isEmpty()) { 
                while (cur != null) { 
                    res.add(cur.val);
                    stack.push(cur);
                    cur = cur.left;
                }
                cur = stack.pop();
                cur = cur.right;
            }
            return res;
        }
    
        public static void main(String[] args) { 
            // 根据给定的数组创建一棵树
            Integer nums[] = {  1, null, 2, 3 };
            TreeNode tree = ConstructTree.constructTree(nums);
            // 将刚刚创建的树打印出来
            TreeOperation.show(tree);
    
            // Integer nums[] = { 5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1 };
            // TreeNode tree = ConstructTree.constructTree(nums);
            // ConstructTree.preOrder(tree);
            // System.out.println();
            // ConstructTree.midOrder(tree);
            // System.out.println();
            // ConstructTree.aftOrder(tree);
            // System.out.println();
    
            // TreeOperation.show(tree);
    
            System.out.println("前序遍历：");
            List<Integer> list = preorderTraversal(tree);
            for (int i = 0; i < list.size(); i++) { 
                System.out.print(list.get(i) + " ");
            }
            System.out.println();
        }
    }

# 参考： #

1.  [【刷题】二叉树非递归遍历][Link 1]
2.  [二叉树——先序遍历（递归/非递归）][Link 2]
3.  [二叉树的非递归前序遍历][Link 3]
4.  [二叉树的前序遍历非递归算法][Link 4]
5.  [二叉树的前序遍历][Link 5]
6.  [史上最全遍历二叉树详解][Link 6]
7.  [彻底吃透前中后序递归法（递归三部曲）和迭代法（不统一写法与统一写法）][Link 7]
8.  [图解 二叉树的四种遍历][Link 8]
9.  [二叉树非递归遍历][Link 9]
10. [递归和迭代][Link 10]

[144.]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/a0f57fc6c43947648b48a56050e823eb.png
[144. 1]: https://zhangyx.blog.csdn.net/article/details/108705982
[94.]: https://zhangyx.blog.csdn.net/article/details/104304658
[145.]: https://zhangyx.blog.csdn.net/article/details/108706556
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/342eeb8c421845b5a354ba1bf77a2bd9.png
[Link 1]: https://juejin.im/post/6844903503807119374
[Link 2]: https://blog.csdn.net/gxx_csdn/article/details/78971630
[Link 3]: https://blog.csdn.net/if_i_were_a/article/details/89215524
[Link 4]: https://blog.csdn.net/qq_39445165/article/details/90743501
[Link 5]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/er-cha-shu-de-qian-xu-bian-li-by-leetcode/
[Link 6]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
[Link 7]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/dai-ma-sui-xiang-lu-chi-tou-qian-zhong-hou-xu-de-d/
[Link 8]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/tu-jie-er-cha-shu-de-si-chong-bian-li-by-z1m/
[Link 9]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/er-cha-shu-fei-di-gui-bian-li-by-beney-2/
[Link 10]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/di-gui-he-die-dai-by-powcai-5/