어떻게 두 갈래 나무 두 노드의 최근 공공 양친을 찾습니까?
우선 이 문제를 구체화하자. 만약에 주어진 나무가 두 갈래로 나무를 찾는다면 이 나무의 일부 성질은 우리가 사용할 수 있을 것이다.코드 보기:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root.val>p.val && root.val>q.val) return lowestCommonAncestor(root.left,p,q);
else if(root.valval && root.valval) return lowestCommonAncestor(root.right,p,q);
else return root;
}
} 이 코드에서 인용에 필요한 판정이 되지 않았음을 주의하고, 퇴고한 후에야 이 위험해 보이는 동작이 사실은 안전하다는 것을 발견하였다.우리는 범위를 두 갈래 찾기 나무로 한정했기 때문에, 만약에
root.val>p.val && root.val>q.val 이 조건이 성립된 것은 이 루트 노드가 반드시 왼쪽 나무가 있다는 것을 의미하기 때문에 루트를 인용한다.left는 안전합니다. 같은 이치로 다음 판단 문장을 검사할 수 있습니다.이어서 우리는 광범위한 의미의 LCA 문제를 토론하고 코드를 보았다.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if( root == p || root == q || root == null)
return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// we found nodes in both the sides, so return root.
if( left != null && right != null )
return root;
return ( left != null )? left : right;
}
}마지막 부분은 더욱 세련되게 통합할 수 있다.
return left == null ? right : right == null ? left : root;이 코드는 논리적으로 두 갈래 나무 전체를 훑어보는 역할을 포함하고 훑어보는 결과를 기록함으로써 노드 간의 관계를 무너뜨리는 사고방식도 교묘하다.
이 문제는 LeetCode OJ - lowest-common-ancestor-of-a-binary-tree - lowest-common-ancestor-of-a-binary-search-tree에서 나왔습니다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
하나의 수조를 깊이가 가장 낮은 두 갈래 나무로 바꾸다문제 정의: Givena sorted(increasing order) array, write an algorithm to create abinary tree with minimal height. 생각: 이 문제는 비...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
