#yyds幹貨盤點# 面試必刷TOP101：二叉樹的中序周遊

1.簡述：

描述

給定一個二叉樹的根節點root，傳回它的中序周遊結果。

資料範圍：樹上節點數滿足 ，樹上每個節點的值滿足 進階：空間複雜度 ，時間複雜度 

示例1

輸入：

{1,2,#,#,3}      

傳回值：

[2,3,1]      

說明：

示例2

輸入：

{}      

傳回值：

[]      

示例3

輸入：

{1,2}      

傳回值：

[2,1]      

說明：

示例4

輸入：

{1,#,2}      

傳回值：

[1,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;
    }
}