Flatten Binary Tree to Linked List

1package pkg5leetcode.top100;2 3/*4 * Flatten Binary Tree to Linked List | LC 1145 * APPROACH: Morris traversal flatten right then left into preorder tail.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class top100_LC114FlattenBinaryTreeToLinkedList {9    /** Same shape as pkg5leetcode/common/TreeNode.java (nested for single-file runs). */10 11    static class TreeNode {12        int val;13        TreeNode left, right;14        TreeNode(int val) { this.val = val; }15    }16 17    static void flatten(TreeNode root) {18        TreeNode cur = root;19        while (cur != null) {20            if (cur.left != null) {21                TreeNode pre = cur.left;22                while (pre.right != null) pre = pre.right;23                pre.right = cur.right;24                cur.right = cur.left;25                cur.left = null;26            }27            cur = cur.right;28        }29    }30 31    static int[] toRightChain(TreeNode root) {32        java.util.List<Integer> list = new java.util.ArrayList<>();33        while (root != null) {34            list.add(root.val);35            if (root.left != null) throw new AssertionError("left not null");36            root = root.right;37        }38        return list.stream().mapToInt(Integer::intValue).toArray();39    }40 41    public static void main(String[] args) {42        TreeNode root = new TreeNode(1);43        root.left = new TreeNode(2);44        root.right = new TreeNode(5);45        root.left.left = new TreeNode(3);46        root.left.right = new TreeNode(4);47        root.right.right = new TreeNode(6);48        flatten(root);49        check(java.util.Arrays.equals(toRightChain(root), new int[]{1, 2, 3, 4, 5, 6}), "case1");50        System.out.println("all tests passed");51    }52 53    static void check(boolean cond, String name) {54        if (!cond) throw new AssertionError("FAILED: " + name);55        System.out.println("  PASS " + name);56    }57}