Slower java version without recursion


  • 0
    S

    public class BinaryTreePaths {

    public List<String> binaryTreePaths(TreeNode root) {
    	List<String> paths = new ArrayList<String>();
    	Stack<TreeNode> node = new Stack<TreeNode>();
    	Stack<Character> mark = new Stack<Character>();
    	char status = 'N';
    	while (root != null) {
    		switch (status) {
    		case 'N': {
    			if (root.left != null) {
    				node.push(root);
    				mark.push('L');
    				root = root.left;
    				status = 'N';
    				continue;
    			}
    			if (root.right != null) {
    				node.push(root);
    				mark.push('R');
    				root = root.right;
    				status = 'N';
    				continue;
    			}
    			//no children, or means it's leaf
    			StringBuilder sb = new StringBuilder();
    			for (int i = 0, l = node.size(); i < l; ++i) {
    				sb.append(node.get(i).val + "->");
    			}
    			sb.append(root.val);
    			paths.add(sb.toString());
    			root = node.empty() ? null : node.pop();
    			status = mark.empty() ? 'N' : mark.pop();
    			continue;
    		}
    		case 'L': {
    			if (root.right != null) {
    				node.push(root);
    				mark.push('R');
    				root = root.right;
    				status = 'N';
    				continue;
    			}
    		}
    		case 'R': {
    			root = node.empty() ? null : node.pop();
    			status = mark.empty() ? 'N' : mark.pop();
    		}
    		}
    	}
    
    	return paths;
    }
    

    }


Log in to reply
 

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