二叉树的所有路径

257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

输入：root = [1]
输出：["1"]

提示：

• 树中节点的数目在范围 [1, 100] 内
• -100 <= Node.val <= 100

迭代法（后序遍历）

访问到叶子节点时栈中元素为根节点到叶子结点的路径

class Solution {
    
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> ans  = new ArrayList<>(); //存放所有路径的集合
        String pathStr = new String();  //存放当前路径的字符串

        if(root==null) return ans;
        Stack<TreeNode> st = new Stack<>();
        TreeNode pre = null;
        //后序遍历
        while(root != null || !st.isEmpty()){
            while(root!=null){
                st.push(root);
                root = root.left;
            }
            root = st.peek(); 
            if(root.right == null || root.right == pre){ //若栈顶元素右节点为空，或右节点已被访问才访问该节点
                if(root.left == null && root.right == null){ //若访问的结点时是叶子节点，输出路径
                    pathStr = "";//初始化路径字符串
                    for(int i = 0 ; i < st.size()-1 ; i++){//栈中元素为根节点到叶子节点的路径
                        TreeNode node = st.get(i);
                        pathStr += String.valueOf(node.val);
                        pathStr += "->";
                    }
                    pathStr += st.peek().val;
                    ans.add(pathStr);
                }
                root = st.pop(); //访问结点出栈
                pre = root;
                root = null;
            }else{
                root = root.right;
            }
        }
        return ans;
    }

}

回溯法

使用先序遍历将所有访问的节点加入到路径path

遍历到叶子节点时，得到一条根节点到叶子结点的路径

若已访问完包含该节点的所有路径，则从路径中删除该节点，可以通过回溯实现

class Solution {
    List<String> ans  = new ArrayList<>(); //存放所有路径的集合
    List<Integer> path = new ArrayList<>(); //存放当前路径的集合
    String pathStr = new String();  //存放当前路径的字符串

    public List<String> binaryTreePaths(TreeNode root) {
        traversal(root, path ,ans);
        return ans;
    }


    //回溯法,前序
    public void traversal(TreeNode root, List<Integer> path , List<String> ans){
        if(root==null) return;
        path.add(root.val);//每遍历一个节点，将其加入到当前路径

        if(root.left==null&&root.right==null){ //左右子树为空，说明该路径已遍历完
           String pathStr = ""; //把路径转换为字符串
           for(int i = 0 ; i < path.size()-1 ; i++){
               pathStr += String.valueOf(path.get(i));
               pathStr += "->";
           }
           pathStr += String.valueOf(path.get(path.size()-1));
           ans.add(pathStr); //把该路径放入到ans集合
           return;
        }
        if(root.left!=null){
            traversal(root.left, path , ans);
            path.remove(path.size()-1); //回溯
        }
        if(root.right!=null){
            traversal(root.right , path , ans);
            path.remove(path.size()-1); //回溯
        }
    }
}