LeetCode-Path Sum III 분석 및 실현 방법

1977 단어 LeetCodePathSum
LeetCode-Path Sum III 분석 및 실현 방법
제목 설명:

You are given a binary tree in which each node contains an integer value.


Find the number of paths that sum to a given value.


The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).


The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.


두 갈래 트리를 지정해서 훑어보는 과정에서 가능한 모든 경로의 합을 수집하고 X와 같은 트리를 찾아낸다.
생각:
현재 노드를 루트로 설정하고 좌우 노드의 경로와 집합을 각각 수집하고merge를 현재 집합에 수집합니다.
현재 노드를 그룹에 추가하여 새로운 가능한 경로를 구성합니다.
구현 코드:

/** 
 * Definition for a binary tree node. 
 * public class TreeNode { 
 * public int val; 
 * public TreeNode left; 
 * public TreeNode right; 
 * public TreeNode(int x) { val = x; } 
 * } 
 */ 
public class Solution { 
 
 private int _sum; 
 private int _count; 
 public int PathSum(TreeNode root, int sum) 
 { 
 _count = 0; 
 _sum = sum; 
 Travel(root, new List<int>()); 
 return _count; 
 } 
 
 private void Travel(TreeNode current, List<int> ret){ 
 if(current == null){ 
  return ; 
 } 
  
 if(current.val == _sum){ 
  _count ++; 
 } 
  
 var left = new List<int>(); 
 Travel(current.left, left); 
  
 var right = new List<int>(); 
 Travel(current.right, right); 
  
 ret.AddRange(left); 
 ret.AddRange(right); 
  
 for(var i = 0;i < ret.Count; i++){ 
  ret[i] += current.val; 
  if(ret[i] == _sum){ 
  _count ++; 
  } 
 } 
 ret.Add(current.val); 
  
 //Console.WriteLine(ret); 
 } 
} 
궁금한 점이 있으면 메시지를 남기거나 본 사이트 지역사회에 가서 토론하세요. 읽어주셔서 감사합니다. 여러분에게 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!

좋은 웹페이지 즐겨찾기