Java BFS Solution


  • 1
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public List<List<String>> printTree(TreeNode root) {
            List<List<String>> res = new ArrayList<>();
            if(root==null) {
                return res;
            }
            
            int depth = maxDepth(root);
            System.out.println(depth);
            
            Queue<TreeNode> nodeQ = new LinkedList<>();
            nodeQ.offer(root);
            Queue<Integer> levelQ = new LinkedList<>();
            levelQ.offer(0);
            List<String> t = new ArrayList<>();
            t.add(String.valueOf(root.val));
            res.add(t);
            int lev = 0;
            
            
            while(!nodeQ.isEmpty()) {
                System.out.println(res);
                int size = nodeQ.size();
                int pos = 0;
                System.out.println("size: "+size);
                if(lev+1 != depth) {
                    List<String> temp = new ArrayList<>();
                    for(int i=0; i<res.get(lev).size(); i++) {
                        temp.add("");
                    }
                    res.add(temp);
                }
                for(int i=0;i<size;i++) {
                    int level = levelQ.poll();
                    TreeNode node = nodeQ.poll();
                    lev = level+1;
                    
                    if(node==null) {
                        if(lev != depth) {
                            nodeQ.offer(null);
                            levelQ.offer(lev);
                            for(int j=0;j<res.size();j++) {
                                res.get(j).add(pos, "");
                            }
                            pos += 2;
                            nodeQ.offer(null);
                            levelQ.offer(lev);
                            for(int j=0;j<res.size();j++) {
                                res.get(j).add(pos, "");
                            }
                            pos += 2;
                        }
                        continue;
                    }
                    
                    if(node.left!=null && lev!=depth) {
                        nodeQ.offer(node.left);
                        levelQ.offer(lev);
                        
                        for(int j=0;j<res.size();j++) {
                            if(j==lev) {
                                res.get(j).add(pos, String.valueOf(node.left.val));
                            }
                            else {
                                res.get(j).add(pos, "");
                            }
                        }
                        pos += 2;
                    }
                    
                    if(node.left==null && lev!=depth) {
                        nodeQ.offer(node.left);
                        levelQ.offer(lev);
                        for(int j=0;j<res.size();j++) {
                            res.get(j).add(pos, "");
                        }
                        pos += 2;
                    }
                    
                    if(node.right!=null && lev!=depth) {
                        nodeQ.offer(node.right);
                        levelQ.offer(level + 1);
                        
                        for(int j=0;j<res.size();j++) {
                            if(j==level+1) {
                                res.get(j).add(pos, String.valueOf(node.right.val));
                            }
                            else {
                                res.get(j).add(pos, "");
                            }
                        }
                        pos += 2;
                    }
                    
                    if(node.right==null && lev!=depth) {
                        nodeQ.offer(node.right);
                        levelQ.offer(lev);
                        for(int j=0;j<res.size();j++) {
                            res.get(j).add(pos, "");
                        }
                        pos += 2;
                    }
                }
                System.out.println(res);
            }
            return res;
        }
        
        private int maxDepth(TreeNode root) {
            if(root==null) {
                return 0;
            }
            
            return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        }
    }
    

  • 0
    X

    @prathak07 Nice solution, you can also refer my java BFS solution using a wrapper treenode class. https://discuss.leetcode.com/topic/100838/java-bfs-solution-using-wrapper-treenode-class


Log in to reply
 

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