Java Solution of iterative postordertraversal


  • 0
    Q

    Postordertraversal can be used to solve this problem. When the current tree node is leaf, the current stack snapshot is then the desired route from root to this leaf, because the non-leaf node which has right child will always be available in stack when its child is visited.

    private List<String> binaryTreePaths(TreeNode root) {
    		List<String> result = new ArrayList<>();
    		
    		TreeNode current = root;
    		if (root == null) {
    			return result;
    		}
    		
    		Stack<TreeNode> stack = new Stack<>();
    		Stack<Boolean> flagStack = new Stack<>();
    		boolean isRightBranchVisited = false;
    		
    		while (true) {
    			while (current != null) {
    				stack.push(current);
    				flagStack.push(false);
    				current = current.left;
    			}
    			
    			if (!stack.empty()) {
    				TreeNode leftLeaf = stack.peek();
    				if (leftLeaf.right == null) {
    					TreeNode[] tn = stack.toArray(new TreeNode[stack.size()]);
    					StringBuilder sb = new StringBuilder();
    					for (int i = 0; i < tn.length - 1; i++) {
    						sb.append(tn[i].val).append("->");
    					}
    					sb.append(tn[tn.length - 1].val);
    					result.add(sb.toString());
    				}
    				current = stack.pop();
    				isRightBranchVisited = flagStack.pop();
    			} else {
    				return result;
    			}		
    			
    			while (current.right == null) {
    				if (!stack.empty()) {
    					current = stack.pop();
    					isRightBranchVisited = flagStack.pop();
    				} else {
    					return result;
    				}		
    				
    				while (isRightBranchVisited) {
    					if (!stack.empty()) {
    						current = stack.pop();
    						isRightBranchVisited = flagStack.pop();
    					} else {
    						return result;
    					}			
    				}
    			}
    						
    			stack.push(current);
    			flagStack.push(true);
    			current = current.right;
    		}
    	} 
    

Log in to reply
 

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