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