每日一题算法：2020年9月4日[二叉树的所有路径]binaryTreePaths

2020年9月4日 二叉树的所有路径 binaryTreePaths

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<String> binaryTreePaths(TreeNode root) { } }

解题思路：

首先对二叉树从根节点开始做深度优先搜索，在深度优先搜索的方法中暂存当前节点的路径字符串，如果当前节点是叶子节点，则将字符串加入结果集。

List<String> res; public List<String> binaryTreePaths(TreeNode root) { res=new ArrayList<>(); buildString(root,new StringBuilder("")); return res; } public void buildString(TreeNode node,StringBuilder path){ if(node==null) return; //如果是叶子节点 if (node.right==node.left){ res.add(path.append(node.val).toString()); } //如果右节点不为空，递归 if (node.right!=null){ StringBuilder newStr=new StringBuilder(path); newStr.append(node.val).append("->"); buildString(node.right,newStr); } if (node.left!=null){ StringBuilder newStr=new StringBuilder(path); newStr.append(node.val).append("->"); buildString(node.left,newStr); } }