Java iterative solution


  • 0
    W

    The basic idea is DFS using stack to record every path to leaf. Also, I use one stringbuilder to track the path in string.

    public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<String>();
        //quick sole
        if(root == null){
            return result;
        }
        
        //initial
        StringBuilder sb = new StringBuilder();
        TreeNode current = root;
        TreeNode pre = root;
        Stack<TreeNode> st = new Stack<TreeNode>();
        
        st.push(current);
        sb.append(current.val);
        
        while(current.left!=null){
            st.push(current.left);
            sb.append("->");
            sb.append(current.left.val);
            current = current.left;
        }
        
        while(!st.empty()){
            if(st.peek().left==null && st.peek().right==null){
                result.add(sb.toString());
            }
            
            if(st.peek().right==null || st.peek().right==pre){
                pre = st.pop();
                sbPop(sb);
            }else{
                current = st.peek().right;
                while(current!=null){
                    st.push(current);
                    sb.append("->");
                    sb.append(current.val);
                    current = current.left;
                }
            }
            
        }
        
        return result;
    }
    
    private void sbPop(StringBuilder sb){
        int index = 0;
        for(int i=sb.length()-1;i>=0;i--){
            if(sb.charAt(i)=='-' && sb.charAt(i+1)=='>'){
                index = i;
                break;
            }
        }
        sb.setLength(index);
    }
    }

Log in to reply
 

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