当前位置：首页 > article >正文

LeetCode100之二叉树的中序遍历(94)--Java

article 2024/11/2 13:59:00

1.问题描述

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

示例1

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

示例2

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

示例3

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

提示

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

难度等级

简单

题目链接

二叉树的中序遍历

2.解题思路

这道题要求我们返回二叉树中序遍历的结果。这道题其实没啥好讲的，中序遍历无非就是先访问左节点，再访问根节点，最后访问右节点，因为根节点是中间访问的，所以叫做中序遍历。

我们之间用一个递归方法递归处理就好了。递归的结束条件是当访问到的结节为空的时候。单层的递归逻辑是先调用递归方法遍历左节点，然后处理根节点（也就是当前的节点），再调用递归方法处理右节点。

        if(root == null){
            return;
        }
        //左
        inorderMethod(root.left,dataList);
        //根(本层的处理逻辑)
        dataList.add(root.val);
        //右
        inorderMethod(root.right,dataList);

因为题目最后要求我们放回一个List集合，所以我们可以将List集合作为方法参数传入递归方法中，再处理根节点的时候，将节点的值存入List集合即可。

    public void inorderMethod(TreeNode root,List<Integer> dataList)

3.代码展示

/**
 * 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 {
    public List<Integer> inorderTraversal(TreeNode root) {
      List<Integer> dataList = new ArrayList<>();
      inorderMethod(root,dataList);
      return dataList;
    }
    public void inorderMethod(TreeNode root,List<Integer> dataList){
        if(root == null){
            return;
        }
        //左
        inorderMethod(root.left,dataList);
        //根(本层的处理逻辑)
        dataList.add(root.val);
        //右
        inorderMethod(root.right,dataList);
    }
   
}