leetcode 257. 二叉树的所有路径

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

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

 

示例 1：

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

示例 2：

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

java 解题思路及代码实现 递归法

package com.java.leetcode.tree;

import com.java.leetcode.compent.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
 *
 * 叶子节点 是指没有子节点的节点。
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [1,2,3,null,5]
 * 输出：["1->2->5","1->3"]
 * 示例 2：
 *
 * 输入：root = [1]
 * 输出：["1"]
 */

public class binaryTreePaths257 {
    /**
     * 思路：
     *  有题目可得 需要获取二叉树的到叶子结点 所有路径 并返回列表
     *  由于是先处理root节点 再探寻叶子结点 可以使用前序遍历的方式
     *
     *  因此 可以将 将路径存放在list 中使用，但是 list 中存储所有节点不能区分 左右节点怎么办
     *  因此 使用回溯的方式：
     *   由二叉树的特性 叶子结点的路径 只有一个，并且父节点 的下游路径至多只有 两个节点
     *   那么通过前序遍历的逻辑
     *   记录路径节点的值
     *   当处理完 叶子节点并记录到 result list中 之后
     *   path 需要将 该叶子结点删除 去获取父节点 另外子节点的路径
     *   依次 类推 通过 遍历 +回溯的方式记录所有节点路径
     * @param root
     * @return
     */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res=new ArrayList<>();
        if(root==null){
            return res;
        }
        List<Integer> path=new ArrayList<>();
        getPath(root,path,res);
        return res;
    }

    /**
     * 递归方式：
     *  1、确定参数：
     *     入参 ： root ,路径 path, 结果result
     *     出参 result void 即可
     *  2、确定终止条件
     *
     */
    public void getPath(TreeNode root,List<Integer> path,List<String> res){
        //前序遍历 获取节点值放入path
        path.add(root.val);
        // 判断是否为叶子节点
        // 若为 叶子结点则对 path组装 获取res 字符串
        if(root.left==null&&root.right==null){
           //组合结果
           StringBuffer sb=new StringBuffer();
           for(int i=0;i<path.size()-1;i++){
               sb.append(path.get(i)).append("->");
           }
           // 拼接最后一个节点
           sb.append(path.get(path.size()-1));
           res.add(sb.toString());
           return;
        }
        //左子树
        if(root.left!=null){
            // 处理左子树
            getPath(root.left,path,res);
            // 处理完成获取path 回溯父节点 子节点删除
            path.remove(path.size()-1);
        }
        if(root.right!=null){
            //处理右子树
            getPath(root.right,path,res);
            //获取右子树结果 回溯上一节点
            path.remove(path.size()-1);
        }

    }
}