导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-257.Binary Tree Paths

题目

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

For example, given the following binary tree:

  1
 /  \
2    3
 \
  5
All root-to-leaf paths are:

[“1->2->5”, “1->3”]

翻译

给出一颗二叉树,返回所有的从根到叶子节点的路径。
例如,给出下列二叉树:
  1
 /  \
2    3
 \
  5
所有的从根到叶子节点的路径为:
[“1->2->5”, “1->3”]

最终结果list的size即为叶子节点个数,当遇到叶子节点时,记录值,并新建list,对于每个节点,其到所有叶子节点的路径为,其左孩子到所有叶子节点的所有路径加上自身,与右子树到所有叶子节点的所有路径之和:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
if (root == null) return new ArrayList<String>();
if (root.left == null && root.right == null) return Arrays.asList(String.valueOf(root.val));

List<String> leftPaths = binaryTreePaths(root.left);
List<String> rightPaths = binaryTreePaths(root.right);
List<String> allPaths = new ArrayList<String>();

for (int i = 0; i < leftPaths.size(); i++) leftPaths.set(i, root.val + "->" + leftPaths.get(i));
for (int i = 0; i < rightPaths.size(); i++) rightPaths.set(i, root.val + "->" + rightPaths.get(i));
allPaths.addAll(leftPaths);
allPaths.addAll(rightPaths);

return allPaths;
}
}

7ms,效率较低,因为过程中涉及了大量不必要的链表操作,且浪费许多空间。
新增加一个函数,遍历二叉树,当遇到叶子节点时更新list,否则递归遍历:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {

List<String> paths = new ArrayList<String>();

public List<String> binaryTreePaths(TreeNode root) {
if (root != null) getPath(root, String.valueOf(root.val));
return paths;
}

private void getPath(TreeNode curNode, String curPath) {
if (curNode.left == null && curNode.right == null) paths.add(curPath);
if (curNode.left != null) getPath(curNode.left, curPath + "->" + curNode.left.val);
if (curNode.right != null) getPath(curNode.right, curPath + "->" + curNode.right.val);
}
}

3ms。

参考:
https://segmentfault.com/a/1190000003465753