作者微信
微

#yyds干货盘点# 面试必刷TOP101：二叉树的中序遍历

小技术 6个月前 (08-18) 0 999+

关注

1.简述：

描述

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

数据范围：树上节点数满足 #yyds干货盘点# 面试必刷TOP101：二叉树的中序遍历，树上每个节点的值满足进阶：空间复杂度，时间复杂度

示例1

输入：

{1,2,#,#,3}

返回值：

[2,3,1]

说明：

示例2

输入：

{}

返回值：

[]

示例3

输入：

{1,2}

返回值：

[2,1]

说明：

示例4

输入：

{1,#,2}

返回值：

[1,2]

说明：

2.代码实现：

import java.util.*;
public class Solution {
    public void inorder(List<Integer> list, TreeNode root){
        //遇到空节点则返回
        if(root == null) 
            return;
        //先去左子树
        inorder(list, root.left); 
        //再访问根节点
        list.add(root.val); 
        //最后去右子树
        inorder(list, root.right); 
    }
    
    public int[] inorderTraversal (TreeNode root) {
        //添加遍历结果的数组
        List<Integer> list = new ArrayList(); 
        //递归中序遍历
        inorder(list, root); 
        //返回的结果
        int[] res = new int[list.size()]; 
        for(int i = 0; i < list.size(); i++)
            res[i] = list.get(i);
        return res;
    }
}