leetcode257二叉树的所有路径

找出所有根节点到叶子结点的路径，这题比较容易想到的是回溯，不过层序遍历用两个队列也可以实现。这里还是只讲回溯

回溯版本一：

递归函数作用：处理传入结点的所有子孙结点，形成以其左右孩子为起点的到各叶子结点的路径。遍历到叶子结点时，组装当前这条路径结果

回溯状态：path集合

递归出口：遍历到叶子结点时，组装当前这条路径结果

第一步：根结点加入path

第二步：将根结点的左孩子结点加入path, 递归处理根结点的左孩子结点，处理完后，移除path中保存的根结点的左孩子结点，此时path中只有根结点

第三步：将根结点的右孩子结点加入path, 递归处理根结点的右孩子结点，处理完后，移除path中保存的根结点的右孩子结点，此时path中只有根结点

class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> res = new ArrayList<>(); //根结点为空，直接返回空集合 if (root == null) return res; //path用来装某条路径上的所有结点 List<Integer> path = new ArrayList<>(); //根结点的值先加入path path.add(root.val); //处理根结点的所有子孙结点，加到相应的路径结果中 dfs(root, path, res); // System.out.println(path); return res; } /** *递归函数作用：处理传入结点的所有子孙结点，形成以其左右孩子为起点的各种到叶子结点的路径。 *遍历到叶子结点时，组装当前这条路径结果 */ private void dfs(TreeNode node, List<Integer> path, List<String> res) { // 如果是叶子结点：把整条路径拼接成字符串 if (node.left == null && node.right == null) { res.add(joinPath(path)); return; } //如果存在左孩子结点 if (node.left != null) { //左孩子结点值加入path path.add(node.left.val); //递归处理左孩子的所有子孙结点 dfs(node.left, path, res); //将path中的左孩子结点值移除 path.remove(path.size() - 1); } //如果存在右孩子结点 if (node.right != null) { //右孩子结点值加入path path.add(node.right.val); //递归处理右孩子的所有子孙结点 dfs(node.right, path, res); //将path中的右孩子结点值移除 path.remove(path.size() - 1); } } //将path中的结点值拼接成想要的字符串 private String joinPath(List<Integer> path) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < path.size(); i++) { if (i > 0) sb.append("->"); sb.append(path.get(i)); } return sb.toString(); } }

remove结点版：

class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> res = new ArrayList<>(); if (root == null) return res; List<TreeNode> path = new ArrayList<>(); path.add(root); dfs(root, path, res); return res; } private void dfs(TreeNode node, List<TreeNode> path, List<String> res) { //如果是叶子结点：把整条路径拼接成字符串 if (node.left == null && node.right == null) { res.add(joinPath(path)); } else { if (node.left != null) { path.add(node.left); dfs(node.left, path, res); path.remove(node.left); } if (node.right != null) { path.add(node.right); dfs(node.right, path, res); path.remove(node.right); } } } private String joinPath(List<TreeNode> path) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < path.size(); i++) { if (i > 0) sb.append("->"); sb.append(Integer.toString(path.get(i).val)); } return sb.toString(); } }

回溯版本二：

递归函数作用：处理传入结点为根的二叉树所有结点，形成传入结点到各叶子结点的路径。遍历到叶子结点时，组装当前这条路径结果

回溯状态：path集合

递归出口：遍历到叶子结点时，组装当前这条路径结果

第一步：将根结点值加入path

第二步：递归处理根结点的左子树

第三步：递归处理根节点的右子树

最后：移除path中根节点值，此时，path为空

为什么最后要移除path中根节点值？

以上图中的左子树为例

左子树根结点的左右孩子处理完成的时候，path中有整颗二叉树的根结点值和其左子树的根结点值，接下来该处理整棵二叉树的右子树了，因此path中左子树的根结点值需要移除掉。

import java.util.*; class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> res = new ArrayList<>(); if (root == null) return res; List<Integer> path = new ArrayList<>(); dfs(root, path, res); return res; } private void dfs(TreeNode node, List<Integer> path, List<String> res) { // 1) 记录当前结点到路径 path.add(node.val); // 2) 如果是叶子结点：把整条路径拼接成字符串 if (node.left == null && node.right == null) { res.add(joinPath(path)); } else { if (node.left != null) dfs(node.left, path, res); if (node.right != null) dfs(node.right, path, res); } // 3) 回溯：撤销当前结点 path.remove(path.size() - 1); } private String joinPath(List<Integer> path) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < path.size(); i++) { if (i > 0) sb.append("->"); sb.append(path.get(i)); } return sb.toString(); } }

remove结点版：

class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> res = new ArrayList<>(); if (root == null) return res; List<TreeNode> path = new ArrayList<>(); dfs(root, path, res); return res; } private void dfs(TreeNode node, List<TreeNode> path, List<String> res) { path.add(node); //如果是叶子结点：把整条路径拼接成字符串 if (node.left == null && node.right == null) { res.add(joinPath(path)); } else { if (node.left != null) { dfs(node.left, path, res); } if (node.right != null) { dfs(node.right, path, res); } } path.remove(node); } private String joinPath(List<TreeNode> path) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < path.size(); i++) { if (i > 0) sb.append("->"); sb.append(Integer.toString(path.get(i).val)); } return sb.toString(); } }

回溯版本三：

这种方式虽然也是对的，但是不标准，推荐版本一和版本二，那种当前层代码移除当前层状态的方式！！！

import java.util.*; class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> res = new ArrayList<>(); if (root == null) return res; List<Integer> path = new ArrayList<>(); dfs(root, path, res); return res; } private void dfs(TreeNode node, List<Integer> path, List<String> res) { // 1) 记录当前结点到路径 path.add(node.val); // 2) 如果是叶子结点：把整条路径拼接成字符串 if (node.left == null && node.right == null) { res.add(joinPath(path)); } else { if (node.left != null) { dfs(node.left, path, res); //移除的是上面代码调用加入的node.left //属于父结点层移除左孩子 path.remove(path.size() - 1); } if (node.right != null){ dfs(node.right, path, res); //移除的是上面代码调用加入的node.right //属于父结点层移除右孩子 path.remove(path.size() - 1); } } } private String joinPath(List<Integer> path) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < path.size(); i++) { if (i > 0) sb.append("->"); sb.append(path.get(i)); } return sb.toString(); } }

remove结点版：

class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> res = new ArrayList<>(); if (root == null) return res; List<TreeNode> path = new ArrayList<>(); dfs(root, path, res); return res; } private void dfs(TreeNode node, List<TreeNode> path, List<String> res) { path.add(node); //如果是叶子结点：把整条路径拼接成字符串 if (node.left == null && node.right == null) { res.add(joinPath(path)); } else { if (node.left != null) { dfs(node.left, path, res); path.remove(node.left); } if (node.right != null) { dfs(node.right, path, res); path.remove(node.right); } } } private String joinPath(List<TreeNode> path) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < path.size(); i++) { if (i > 0) sb.append("->"); sb.append(Integer.toString(path.get(i).val)); } return sb.toString(); } }