Level order traversal wrapping Nodes with a shift index


  • 0
    A

    The problem with recursive solution is how to keep the order within one shift, since there seems to be no option of level order traversal in doing recursion. I mean case [1,2,3,null,5,6,7,8,null,null,11] will result in one array having [11, 3] with simple recursive implementation. For that I had to try iterative and wrap each node with a shift index. Can any one solve this problem more concisely?

    I think the time complexity of the problem is O(N) time & O(N) space. Please point out if I am wrong.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public class TreeNode1 {
            TreeNode node;
            int shift;
            public TreeNode1 (TreeNode node, int shift) {
                this.node = node;
                this.shift = shift;
            }
        }
        public List<List<Integer>> verticalOrder(TreeNode root) {
            if (root == null) return new ArrayList<List<Integer>>();
            TreeMap<Integer, List<Integer>> tm = new TreeMap<> ();
            traverse(tm, root);
            List<List<Integer>> results = new ArrayList<>();
            for (Integer i : tm.keySet()) results.add(tm.get(i));
            return results;
        }
        public void traverse(TreeMap<Integer, List<Integer>> tm, TreeNode n) {
            LinkedList<TreeNode1> ll = new LinkedList<>();
            ll.add (new TreeNode1(n, 0));
            while (!ll.isEmpty()) {
                    TreeNode1 tn = ll.poll();
                    if (!tm.containsKey(tn.shift)) 
                        tm.put(tn.shift, new ArrayList<Integer>());
                    tm.get(tn.shift).add(tn.node.val);
                    if (tn.node.left != null) ll.add(new TreeNode1(tn.node.left , tn.shift - 1));
                    if (tn.node.right != null)ll.add(new TreeNode1(tn.node.right, tn.shift + 1));
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.