Java BFS Solution Using Wrapper TreeNode class


  • 0
    X
        //Wrapper class: TreeNode with index range
        class Node {
            TreeNode left;
            TreeNode right;
            String val;
            int start, end;
            Node (TreeNode node, int start, int end) { 
                this.val = String.valueOf(node.val);
                this.left = node.left;
                this.right = node.right;
                this.start = start;
                this.end = end;
            }
        }
    
        public List<List<String>> printTree(TreeNode root) {
            List<List<String>> res = new ArrayList();
            if (root == null) return res;
            int depth = getDepth(root);
            // int colCount = Math.pow(2, depth) - 1;
            int colCount = (int)Math.pow(2, depth) - 1;
            List<String> row = new ArrayList();
            for (int i = 0; i < colCount; i++) row.add("");
            for (int i = 0; i < depth; i++) res.add(new ArrayList(row));
            
            Queue<Node> q = new LinkedList();
            q.offer(new Node(root, 0, colCount - 1));
            
            int level = 0;
            while (!q.isEmpty()) {
                int size = q.size();
                for (int i = 0; i < size; i++) {
                    Node temp = q.poll();
                    int low = temp.start;
                    int high = temp.end;
                    int mid = low + (high - low) / 2;
                    res.get(level).set(mid, temp.val);
                    if (temp.left != null) q.offer(new Node(temp.left, low, mid - 1));
                    if (temp.right != null) q.offer(new Node(temp.right, mid + 1, high));
                }
                level++;
            }
            return res;
        }
    

Log in to reply
 

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