Non-recursive Java solution. With help of a stack and a set


  • 0
    F
    public List<String> binaryTreePaths(TreeNode root){
    	if (root == null)
    		return new ArrayList<String>();
    	Set<TreeNode> hasVisited = new HashSet<TreeNode>();
    	List<String> ret = new ArrayList<String>();
    
    	while (!hasVisited.contains(root)) {
    
    		StringBuilder sb = new StringBuilder();
    		Stack<TreeNode> s = new Stack<TreeNode>();
    		s.push(root);
    
    		while (!s.empty()) {
    			TreeNode n = s.pop();
    			if (n.left == null && n.right == null) {
    				sb.append(n.val);
    				ret.add(sb.toString());
    				hasVisited.add(n);
    				break;
    			} else {
    				sb.append(n.val + "->");
    				if (n.right != null && !hasVisited.contains(n.right)) {
    					s.push(n.right);
    					continue;
    				}
    				if (n.left != null && !hasVisited.contains(n.left)) {
    					s.push(n.left);
    					continue;
    				}
    				hasVisited.add(n);
    				break;
    
    			}
    		}
    	}
    	return ret;
    }

Log in to reply
 

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