[LeetCode] 257. Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

Input:

   1
 /   
2     3
 
  5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

二叉树路径。题意是给一个二叉树，请输出从根节点遍历到每个最小的叶子节点的路径。这个题思路跟path sum的头两个版本非常像。

[LeetCode] 112. Path Sum

[LeetCode] 113. Path Sum II

此题可以用二叉树的先序遍历的思想做，参见144题。我给出的是递归的解法。

时间O(n)

空间O(h) - 树的高度

此处解释一下helper函数。14行如果再也没有左右孩子了，就直接把当前节点的值加入结果集；如果还有左孩子（17行）或者右孩子（20行），递归的参数就需要加上"->"。因为知道后面还会再加上孩子节点的值。举个例子，根节点1有左孩子2，所以他在遍历到18行的时候，带入的参数是(res, root.left, path + 1 + '->') === (res, root.left, '1 - >')。遍历到2的时候，因为有右孩子，所以遍历到21行的时候，带入的参数是(res, root.right, '1 ->' + 2 + '->')

JavaScript实现

 1 /**
 2  * @param {TreeNode} root
 3  * @return {string[]}
 4  */
 5 var binaryTreePaths = function(root) {
 6     let res = [];
 7     if (root === null) return res;
 8     // normal case
 9     helper(res, root, '');
10     return res;
11 };
12 
13 var helper = function(res, root, path) {
14     if (root.left === null && root.right === null) {
15         res.push(path + root.val);
16     }
17     if (root.left !== null) {
18         helper(res, root.left, path + root.val + '->');
19     }
20     if (root.right !== null) {
21         helper(res, root.right, path + root.val + '->');
22     }
23 };

Java实现

 1 class Solution {
 2     public List<String> binaryTreePaths(TreeNode root) {
 3         List<String> res = new ArrayList<>();
 4         if (root == null) {
 5             return res;
 6         }
 7         helper(res, root, "");
 8         return res;
 9     }
10 
11     private void helper(List<String> res, TreeNode root, String path) {
12         if (root.left == null && root.right == null) {
13             res.add(path + root.val);
14         }
15         if (root.left != null) {
16             helper(res, root.left, path + root.val + "->");
17         }
18         if (root.right != null) {
19             helper(res, root.right, path + root.val + "->");
20         }
21     }
22 }

LeetCode 题目总结