package binarytree.inordertraversal;
import binarytree.untils.GenerateTreeNode;
import binarytree.untils.TreeNode;
import java.util.ArrayList;
import java.util.List;
/**
* 给定一个二叉树的根节点 root ,返回它的 中序 遍历。
*
*
*
* 示例 1:
*
*
* 输入:root = [1,null,2,3]
* 输出:[1,3,2]
* 示例 2:
*
* 输入:root = []
* 输出:[]
* 示例 3:
*
* 输入:root = [1]
* 输出:[1]
* 示例 4:
*
*
* 输入:root = [1,2]
* 输出:[2,1]
* 示例 5:
*
*
* 输入:root = [1,null,2]
* 输出:[1,2]
*
*
* 提示:
*
* 树中节点数目在范围 [0, 100] 内
* -100 <= Node.val <= 100
*
*
* 进阶: 递归算法很简单,你可以通过迭代算法完成吗?
*/
public class InOrderTraversal {
/**
* 左根右
* 举个例子 1,2,3,4,5,6,7
* 中序遍历 4 2 5 1 6 3 7
* @param root
* @return
*/
public static List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inorder(root,res);
return res;
}
private static void inorder(TreeNode root,List<Integer> res){
if(root == null){
return;
}
inorder(root.left,res);//左
res.add(root.val);//根
inorder(root.right,res);//右
}
public static void main(String[] args) {
Integer[] nums = {1,null,2,3};
TreeNode treeNode = GenerateTreeNode.generateTreeNode(nums);
List<Integer> res = inorderTraversal(treeNode);
for (int i = 0; i < res.size(); i++) {
System.out.println(res.get(i));
}
}
}
不会,我可以学;落后,我可以追赶;跌倒,我可以站起来!