Anyone could please improve my iterative algorithm. (iterate with Queue)


  • 0
    Y
    /**
     * 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<String> binaryTreePaths(TreeNode root) {
            List<String> result = new ArrayList<>();
            if(root == null) return result;
            // define queues, one for nodes and another for StringBuilder
            Queue<TreeNode> nodeQ = new LinkedList<>();
            Queue<StringBuilder> sbQ = new LinkedList<>();
            nodeQ.offer(root);
            sbQ.offer(new StringBuilder().append(root.val));
            // use queues
            while(!nodeQ.isEmpty()){
                final int qSize = nodeQ.size();
                for(int i=0; i<qSize; i++){
                    TreeNode currentNode = nodeQ.poll();
                    StringBuilder currentSb = sbQ.poll();
                    if(currentNode.left == null && currentNode.right == null){
                        result.add(currentSb.toString());
                        continue;
                    }
                    
                    if(currentNode.left != null){
                        nodeQ.offer(currentNode.left);
                        StringBuilder tempSb = new StringBuilder(currentSb.toString());
                        tempSb.append("->").append(currentNode.left.val);
                        sbQ.offer(tempSb);
                    }
                    
                    if(currentNode.right != null){
                        nodeQ.offer(currentNode.right);
                        StringBuilder tempSb = new StringBuilder(currentSb.toString());
                        tempSb.append("->").append(currentNode.right.val);
                        sbQ.offer(tempSb);
                    }
                }
            }
            return result;
        }
    

  • 0

    we share the same idea, BFS

    public List<String> binaryTreePaths(TreeNode root){
    		if(root == null) return new LinkedList<String>();
    		String s = "" + root.val;
    		List<String> list = new LinkedList<String>();
    		
    		//if both null, no further operation
    		if(root.left == null && root.right == null){
    			list.add(s);
    			return list;
    		}
    		
    		Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
    		Queue<String> pathQueue = new LinkedList<String>();
    		
    		//push children into queue
    		if(root.left != null){
    			nodeQueue.offer(root.left);
    			pathQueue.offer(s);
    		}
    		if(root.right != null){
    			nodeQueue.offer(root.right);
    			pathQueue.offer(s);
    		}
    		
    		while(!nodeQueue.isEmpty()){
    			TreeNode temp = nodeQueue.peek();
    			String tempPath = pathQueue.peek();
    			tempPath += "->" + temp.val;
    			//both children null, end of this path
    			if(temp.left == null && temp.right == null){
    				list.add(tempPath);
    			}
    			else {
    				//find out sub path
    				if(temp.left != null){
    					nodeQueue.offer(temp.left);
    					pathQueue.offer(tempPath);
    				}
    				if(temp.right != null){
    					nodeQueue.offer(temp.right);
    					pathQueue.offer(tempPath);
    				}
    			}
    			nodeQueue.poll();
    			pathQueue.poll();
    		}
    		return list;
    	}
    

Log in to reply
 

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