Binary Tree Inorder Traversal

1package pkg5leetcode.interview150;2 3/*4 * Binary Tree Inorder Traversal | LC 945 * APPROACH: Recursive left-root-right traversal.6 * COMPLEXITY: Time O(n), Space O(h)7 */8import java.util.*;9 10public class interview150_LC94BinaryTreeInorderTraversal {11    /** Same shape as pkg5leetcode/common/TreeNode.java (nested for single-file runs). */12 13    static class TreeNode {14        int val;15        TreeNode left, right;16        TreeNode(int val) { this.val = val; }17    }18 19    static List<Integer> inorderTraversal(TreeNode root) {20        List<Integer> res = new ArrayList<>();21        inorder(root, res);22        return res;23    }24 25    static void inorder(TreeNode node, List<Integer> res) {26        if (node == null) return;27        inorder(node.left, res);28        res.add(node.val);29        inorder(node.right, res);30    }31 32    public static void main(String[] args) {33        TreeNode root = new TreeNode(1);34        root.right = new TreeNode(2);35        root.right.left = new TreeNode(3);36        check(inorderTraversal(root).equals(Arrays.asList(1, 3, 2)), "case1");37        check(inorderTraversal(null).isEmpty(), "case2");38        System.out.println("all tests passed");39    }40 41    static void check(boolean cond, String name) {42        if (!cond) throw new AssertionError("FAILED: " + name);43        System.out.println("  PASS " + name);44    }45}