leetcode_129_Sum Root to Leaf Numbers
설명:
Given a binary tree containing digits from
0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path
1->2->3 which represents the number 123 . Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path
1->2 represents the number 12 . The root-to-leaf path 1->3 represents the number 13 . Return the sum = 12 + 13 =
25 . 생각:
pathsum 시리즈와 같은 사고방식이다. 뒤에 어떤 노드에 옮겨다니고root-to-leaf의 모든 결점의 값을 하나의 수와sum를 더하여 모든leaf결점을 옮겨다니고sum로 되돌아간다.
코드:
public int sumNumbers(TreeNode root) {
if (root == null)
return 0;
int temp=0,sum=0;
LinkedList<TreeNode>linkedList=new LinkedList<TreeNode>();
Stack<TreeNode> st1 = new Stack<TreeNode>();
linkedList.addLast(root);
TreeNode top = null;
while (!linkedList.isEmpty()) {
top=linkedList.getLast();
while(top.left!=null)//
{
linkedList.addLast(top.left);
top=top.left;
}
while(!linkedList.isEmpty())
{
top=linkedList.getLast();
if(top.right==null)// ，
{
if(top.left==null)
{
temp=0;
for(int i=0;i<linkedList.size();i++)
temp=temp*10+linkedList.get(i).val;
sum+=temp;
}
linkedList.removeLast();
}else
{
if(st1.empty()||(!st1.empty()&&st1.peek()!=top))// ， ， st1
{
st1.push(top);
linkedList.addLast(top.right);
break;// ，
}
else// ， ，
{
st1.pop();
linkedList.removeLast();
}
}
}
}
return sum;
}결과:
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
leetcode_129_Sum Root to Leaf NumbersGiven a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is th...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
