【算法题】二叉树的中序遍历

二叉树的中序遍历

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

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：

public class LC019_94_inorderTraversal_01 {
    static List<Integer> ans = new ArrayList<>();
    public static void main(String[] args) {
        TreeNode tree = TreeNode.createTree();
        TreeNode.printTree(tree);
        List<Integer> integers = inorderTraversal(tree);
        for (Integer integer : integers) {
            System.out.println(integer);
        }
    }
    //中序遍历,先遍历根节点
    public static List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return ans;
        }
        inorderTraversal(root.left);
        ans.add(root.val);
        inorderTraversal(root.right);
        return ans;
    }
}

public class LC019_94_inorderTraversal_02 {


    public static void main(String[] args) {
        TreeNode tree = TreeNode.createTree();
        TreeNode.printTree(tree);
        List<Integer> integers = inorderTraversal(tree);
        for (Integer integer : integers) {
            System.out.println(integer);
        }
    }


    //中序遍历,先遍历根节点
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        while (!queue.isEmpty() || root != null) {
            if (root != null) {
                queue.add(root);
                root = root.left;
            } else {
                //取出最后添加的,优先输出
                TreeNode poll = queue.pollLast();
                ans.add(poll.val);
                root = poll.right;
            }
        }
        return ans;
    }
}