leetcode 1028. 두 갈래 나무를 순서대로 옮겨다니다
해법
1. 귀속
나무의 선착순과 관련된 것은 바로 귀속을 생각했다. 다음은 두 갈래 나무의 선착순에 따라 쓰는 귀속 방법이다.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
//
public TreeNode dfs(String s,int[] index,int deep){
if(index[0]>=s.length())return null;
// 。
int hh=0,i=index[0],n=s.length();
while (i<n&&s.charAt(i)=='-'){
hh++;
i++;
}
if(hh!=deep)return null;
//
int dd=0;
while(i<n&&s.charAt(i)!='-'){
dd=dd*10+s.charAt(i)-'0';
i++;
}
TreeNode node = new TreeNode(dd);
index[0]=i;
node.left = dfs(s,index,deep+1);
node.right = dfs(s,index,deep+1);
return node;
}
public TreeNode recoverFromPreorder(String S) {
return dfs(S,new int[]{
0},0);
}
}
4
TreeNode dfs(String s,int[] index,int deep) 그 중에서 s는 전송된 문자열이고 index는 문자열이 다음 단계에 스캔된 하표이다. 자바에서 함수에서 기본 형식의 값을 바꿀 수 없기 때문에 수조로 봉인한다.deep은 이때의 깊이를 나타냅니다. 문자열에서 얻은 깊이 (즉 읽은 '-' 의 개수) 가 deep와 일치하면 다음에 스캔한 데이터가 이때에 귀속되는 노드임을 나타냅니다.2. 교체
귀환의 장점은 간단하고 이해하기 쉬우나 효율적으로 말하자면 귀환을 최대한 피해야 하며 모든 귀환은 교체로 실현될 수 있다.위의 계산은 많은 불필요한 점을 볼 수 있다. 예를 들어 깊이를 계산할 때 깊이가 deep와 일치하지 않을 때 계산 과정은 여러 번 나타난다.교체 코드는 다음과 같다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
5. 문자열 s를 지정하고 s에서 가장 긴 메모 문자열을 찾습니다.너는 s의 최대 길이가 1000이라고 가정할 수 있다.(dp)dp방정식 dp[i][j]는 i부터 j까지 회문열 을 대표한다 dp[i][i]=1; if(s[i]==s[i+1]) dp[i][i+1]=1; s[i]==s[i+len] && dp[i+1][i+len-1]==1 => d...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
