LeetCode 검지 offer Q68-ll 두 갈래 나무의 최근 조상

생각

이어서 67번.이 문제는 일반적인 상황이다. 바로 평범한 두 갈래 나무가 순서가 없다는 것이다.그럼 어떻게 구해요?

비교적 쉽게 떠오르는 것은 dfs로 pq에 도착하는 두 가지 경로를 찾은 다음에 가장 가까운 공통점을 비교하는 것이다.그러나 이런 방법은 귀속이 끝난 후에도 처리 효율이 비교적 낮다..

우리는 귀속 함수 dfs1)현재 노드 루트가 p 또는 q일 때 이 노드를 직접 되돌려줍니다.2) 각각 루트에 들어간 좌우 트리로 돌아가 두 노드 left와right를 얻는다.이 두 노드는 좌우 트리에 p 또는 q가 함유되어 있는지 여부를 나타낸다

i. left right p q， root ，root 。
ii.  left=null right=null， root pq ， return null。 
iii.  left right null null， null , 。

코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        if(root.val==p.val) return p;
        if(root.val==q.val) return q;
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);

        if(left==null&&right==null) return null;
        if(left!=null&&right!=null)
        return root;
        return left!=null?left:right;
    }
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

【LeetCode】114. Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place. For example, given the following tree: The flattened tree sho...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

LeetCode 검지 offer Q68-ll 두 갈래 나무의 최근 조상

생각

코드

좋은 웹페이지 즐겨찾기