[LeetCode] 257. Binary Tree Paths

3435 단어
두 갈래 나무 경로.제목은 두 갈래 나무에 뿌리 노드에서 가장 작은 잎 노드까지의 경로를 출력하는 것입니다.예제
Example:
Input:

   1
 /   \
2     3
 \
  5

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

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

이 문제는 두 갈래 나무의 선차적인 사상으로 풀 수 있으며 144문제 참조.내가 제시한 것은 귀속의 해법이다.
시간 O(n)
공간 O(n)
여기에 helper 함수를 설명합니다.14줄에 더 이상 좌우 아이가 없으면 현재 노드의 값을 결과집에 넣는다.만약 왼쪽 아이(17줄) 또는 오른쪽 아이(20줄)가 있다면, 귀속 매개 변수는 "->"를 추가해야 한다.뒤에 아이 노드의 값까지 더해질 줄 알았기 때문이다.
 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 };

좋은 웹페이지 즐겨찾기