二叉树的中序遍历
简单
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
题解（中序遍历：左根右）
先构建一棵二叉树
编写中序遍历方法
先判断节点左子树是否为空，不为空则递归该方法（传入该节点左孩子节点，与集合变量）
输出节点的值到集合
在判断节点右子树是否为空，不为空则递归该方法（传入该节点右孩子节点，与集合变量）
public class BinaryTree {public static void main(String[] args) {System.out.println(inorderTraversal());}public static List<Integer> inorderTraversal() {TreeNode root = new TreeNode(1);TreeNode b = new TreeNode(2);TreeNode c = new TreeNode(3);
// Node d = new Node(4, "D");root.right = b;b.left = c;List<Integer> list = new ArrayList<>();System.out.println("中序遍历");infixOrder(root,list);return list;}public static void infixOrder(TreeNode root,List<Integer> list) {if (root.left != null) {infixOrder(root.left,list);}// 输出父节点
// System.out.println(this);list.add(root.val);if (root.right != null) {infixOrder(root.right,list);}}}class TreeNode {public List<Integer> list = new ArrayList<Integer>();public int val;public TreeNode left;public 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;}// 中序遍历 左根右@Overridepublic String toString() {return "TreeNode{" +"val=" + val +'}';}
}
