257. All paths of binary tree

Force link

subject

Give you the root node of a binary tree root , Press In any order , Return all paths from the root node to the leaf node .

Leaf node A node without children .

Example 1：

Input ：root = [1,2,3,null,5]
Output ：[“1->2->5”,“1->3”]
Example 2：

Input ：root = [1]
Output ：[“1”]

Tips ：

The number of nodes in the tree is in the range [1, 100] Inside
-100 <= Node.val <= 100

Their thinking

Find the way , It seems that there is something wrong with traversal no matter how ：
After finding the first leaf node , How to get back , Continue to traverse the next leaf Node ? This requires backtracking .
Record the traversed path with an array , Find the leaf node , Go back to the previous node .
Use recursion to solve , Where to recurse , Where to go back .

Code implementation

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        
        List<Integer> list = new ArrayList<>();
        List<String> result = new ArrayList<>();
        if(root == null) return result;
        digui(list,result,root);
        return result;   
    }

    void digui(List<Integer> list,List<String> result,TreeNode r){
            list.add(r.val);
            if( r.left ==null && r.right == null){  
                String ss = "";
                for(int i=0;i<list.size();i++){
                    ss = ss + Integer.toString(list.get(i));
                    if(i!=list.size()-1){
                        ss = ss + "->";
                    }
                }
                result.add(ss);
                return;
            }
            if(r.left != null){
                digui(list,result,r.left);
                list.remove(list.size()-1);
            }
             if(r.right != null){
                digui(list,result,r.right);
                list.remove(list.size()-1);
            }   
    }
}