【LeeCode】94. 二叉树的中序遍历

【题目描述】

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

​​​https://leetcode.cn/problems/binary-tree-inorder-traversal/description/?favorite=2cktkvj​​

​

【示例】

【代码】

package com.company;
import java.util.*;

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;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        dfs(res, root);
        return res;
    }

    private void dfs(List<Integer> res, TreeNode root) {
        if (root == null) return;
        // 中序： 左 输 右
        dfs(res, root.left);
        res.add(root.val);
        dfs(res, root.right);
    }
}
public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>(Arrays.asList(
            new Integer[]{
                    1, null, 2, 3
            }
        ));
        TreeNode tree = createBinaryTree(list);
        List<Integer> result = new TreeNode().inorderTraversal(tree);
        System.out.println(result.toString());
    }
    public static TreeNode createBinaryTree(LinkedList<Integer> list) {
        TreeNode res = null;
        if (list == null || list.isEmpty()){
            return null;
        }

        Integer data = list.removeFirst();

        if (data != null){
            res = new TreeNode(data);
            res.left = createBinaryTree(list);
            res.right =createBinaryTree(list);
        }
        return res;
    }
}