leetcode337. House Robber III
1398 단어 leetcode
사고방식: 두 갈래 나무에 대해 조건에 따라 이 두 갈래 나무 뿌리 노드가 취할 수 있다고 판단하면 매개 변수true를 전달하고 만약에 어떤 두 갈래 나무의 뿌리 노드가 취할 수 없다면false를 전달한다. 매개 변수가true일 때 도대체 두 가지 상황으로 나눌 수 있는지 없는지는 0-1가방 문제와 유사하다. 그리고 그 결과가 비교적 큰 상황으로 돌아간다.매개 변수가false이면 루트 노드를 찾을 수 없을 것입니다. (root.left,true) + (root.right,true) 로 돌아갑니다.
나는 순전히 귀속적으로 쓴 것으로 효율이 비교적 낮을 수 있다.leetcode에 제출하면 시간이 1000ms를 넘지만 사고가 상대적으로 간단하다.
내 leetcode의 모든 코드는 github에 넣었습니다.https://github.com/gaohongbin/leetcode
코드:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int rob(TreeNode root) {
if(root == null)
return 0;
return helper(root,true);
}
public int helper(TreeNode root,boolean flag){ //flag true root ，flag false root
if(root == null)
return 0;
if(flag == false){ // root
int left = helper(root.left,true);
int right = helper(root.right,true);
return left+right;
}
else{ //root
int hasRoot = root.val + helper(root.left,false)+helper(root.right,false); // root
int noRoot = helper(root.left,true)+helper(root.right,true);// root
if(hasRoot>noRoot)
return hasRoot;
return noRoot;
}
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
