[LeetCode] 112. Path Sum
Example:
Given the below binary tree and
sum = 22 , 5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path
5->4->11->2 which sum is 22. DFS, 비교적 직관적이어서 바로 코드를 눌렀습니다.
1 /**
2 * Definition for a binary tree node.
3 * function TreeNode(val) {
4 * this.val = val;
5 * this.left = this.right = null;
6 * }
7 */
8 /**
9 * @param {TreeNode} root
10 * @param {number} sum
11 * @return {boolean}
12 */
13 var hasPathSum = function(root, sum) {
14 if (root === null) return false;
15 if (root.left === null && root.right === null) return sum === root.val;
16 return (
17 hasPathSum(root.left, sum - root.val) ||
18 hasPathSum(root.right, sum - root.val)
19 );
20 };BFS
queue로 옮겨다니는 노드를 저장합니다.어떤 노드에 가입할 때 만약에 이 노드에 아이 노드가 없다면 이 노드에 가입한 후의 값이sum인지 판단해야 한다.만약 이 노드에 아이 노드가 있다면, 이어서 아이 노드를 두루 훑어보면cur.val + cur.left.val(cur.val +cur.right.val)에queue를 추가합니다.
1 /**
2 * @param {TreeNode} root
3 * @param {number} sum
4 * @return {boolean}
5 */
6 var hasPathSum = function(root, sum) {
7 if (!root) return false;
8 let queue = [root];
9 while (queue.length) {
10 let cur = queue.shift();
11 if (!cur.left && !cur.right && cur.val === sum) {
12 return true;
13 }
14 if (cur.left) {
15 cur.left.val += cur.val;
16 queue.push(cur.left);
17 }
18 if (cur.right) {
19 cur.right.val += cur.val;
20 queue.push(cur.right);
21 }
22 }
23 return false;
24 };이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
