数据结构之递归-如何巧妙利用递归函数的返回值

下面以一个例题为例进行阐述。

给定一棵二叉树，返回所有表示从根结点到叶子结点路径的字符串。

解析：该过程用递归实现更好理解和处理，要得到由1为根，5和3为叶子节点的所有路径组成的字符串，我们只需要用1->拼接上其左右子树对应的路径即可，于是问题就向下延伸，变成了分别找以2和3为根结点的路径字符串，以此类推，直到树的叶子节点。这个过程是一个压栈（非叶子节点）和弹栈的过程（叶子节点），弹栈后就露出叶子节点对应的父节点（即临时根结点），之后开始组装需要字符串，待该父节点的所有子树的字符串都组装好了，逐步回溯到最终的根结点，完成最后的拼接。见下图二叉树，

输出结果为[“1->2->5”,“1->3”]。

import java.util.LinkedList; import java.util.List; public class LC257 { // 利用递归算法和回溯的思想，这是利用树的深度优先遍历 public List<String> binaryTreePaths(TreeNode root) { List<String> result = new LinkedList<String>(); // 递归终止条件1 if (null == root) return result; // 递归终止条件2，将叶子结点添加中间结果中，以便该叶子节点的父节点拼接临时字符串用 if (null == root.left && null == root.right) { result.add(String.valueOf(root.val)); return result; } // 递归处理当前结点的左子树 List<String> resultL = binaryTreePaths(root.left); // 将当前结点与其左子树结点连接 for (int l = 0; l < resultL.size(); ++l) result.add(String.valueOf(root.val) + "->" + resultL.get(l)); // 递归处理当前结点的右子树 List<String> resultR = binaryTreePaths(root.right); // 将当前结点与其右子树结点连接 for (int r = 0; r < resultR.size(); ++r) result.add(String.valueOf(root.val) + "->" + resultR.get(r)); return result; } public static void main(String[] args) { TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); root.right.left = new TreeNode(6); System.out.println("result=" + new LC257().binaryTreePaths(root)); } }