蓝桥与力扣刷题（94 二叉树的中序遍历）

题目：给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

解题思路＋代码：

代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> result = new ArrayList<>(); //new一个全局数组变量
    public List<Integer> inorderTraversal(TreeNode root) {
        /**
        思路：二叉树的中序遍历顺序（左根右）--(深度优先遍历DFS)
        创建DFS方法
        1.首先判断根节点是否为空，为空直接返回
        2.根据二叉树中序遍历顺序（左根右）依次遍历并添加数据
         */
       dfs(root); //调用
       return result;
    }

    public void dfs(TreeNode node){
        //判断根节点是否为空，为空直接返回
        if(node == null){
            return ;
        }
        dfs(node.left); //遍历左子树
        result.add(node.val); //访问根节点
        dfs(node.right); //遍历右子树
    }
}

总结：这题首先需要知道二叉树的遍历顺序（先序：根左右；中序：左根右；后序：左右根）（深度优先搜索DFS），本题明确了是二叉树的中序遍历。解答该题有多种方法，但是使用递归方法是解答中最高效的。递归利用了函数调用栈的特性，很自然地模拟了深度优先搜索（DFS）的过程。