LeetCode：二叉树的遍历（递归）(java)

逃离我推掉我的手 2023-07-17 02:51 4阅读 0赞

# 一. 题目描述 #

给定一个二叉树，返回它的前序遍历。

**示例:**

**输入:** \[1,null,2,3\]

1
        \
         2
        /
       3

**输出:** \[1,2,3\]

**原题链接：**[link][].

# 二. 前序遍历代码 #

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
     //主函数：本题目需要在嵌套函数外新建一个数组，故创建此主函数
    class Solution { 
      public List<Integer> preorderTraversal(TreeNode root) { 
       //new一个数组list.其中<Integer>为整型，ArrayList为数组.
       List<Integer> list = new ArrayList<Integer>();
       //调用函数helper
       helper(root,list);
        //return
       return list;  
       }
       //helper函数
       private void helper(TreeNode root, List<Integer> list){ 
           if(root==null){ 
               return;
           }
           list.add(root.val);//位置1：前序遍历位置
           if(root.left!=null){ 
               helper(root.left,list);
           }
            //位置2：中序遍历位置
            if(root.right!=null){ 
               helper(root.right,list);
           }
           //位置3：后序遍历位置
       }
    }

# 三. 思路 #

#### 1.先设置嵌套出口 ####

当极端情况下：root==null时，退出。

if(root==null){
       return;
     }

#### 2.再设置嵌套入口 ####

if(root.left!=null){//若root左节点存在，则进入左节点
         helper(root.left,list); //设置入口
     }
      if(root.right!=null){//若root右节点存在，则进入右节点
       helper(root.right,list);//设置入口
      }

#### 3.问题处理 ####

将结点root的值存入数组中。

list.add(root.val);

# 四. 知识拓展 #

#### 1. List ####

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

**四个集合：**

**ArrayList :** 基于数组实现的非线程安全的集合。查询元素快，插入，删除中间元素慢。  
**LinkedList :** 基于链表实现的非线程安全的集合。查询元素慢，插入，删除中间元素快。  
**Vector :** 基于数组实现的线程安全的集合。线程同步（方法被synchronized修饰），性能比ArrayList差。  
**CopyOnWriteArrayList :** 基于数组实现的线程安全的写时复制集合。线程安全（ReentrantLock加锁），性能比Vector高，适合读多写少的场景

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

**四种方法：**

添加方法是：**.add(e)**；　  
获取方法是：**.get(index)**；　　  
删除方法是：**.remove(index)**；  
按照索引删除: **.remove(Object o)**；

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

#### 2. 中序及后序遍历 ####

只需要改变下行代码的位置：

list.add(root.val);

见“**二. 前序遍历代码**”。位置1：前序遍历位置； 位置2：中序遍历位置； 位置3：后序遍历位置；

[link]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/