[트리] Lowest Common Ancestor of a Binary Tree(귀속)

2078 단어
제목:
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).” 
        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes  5  and  1  is  3 . Another example is LCA of nodes  5  and  4  is  5 , since a node can be a descendant of itself according to the LCA definition.
생각:
노드 a와 노드 b의 공공 조상 c는 반드시 만족한다. a와 b는 각각 c의 좌우 나무에 나타난다.또는 a, b측은 조상 원소다.
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if(root==null){
        return;
    }
    if(root==p||root==q){
        return root;
    }
    
    var l=lowestCommonAncestor(root.left,p,q);
    var r=lowestCommonAncestor(root.right,p,q);
    
    if(l&&r){
        return root;
    }else{
        return l?l:r;
    }
    
};

서브셋 생성(bit, 귀속, 서브셋 생성)
[AWS][초보자]wordpress의 블로그 시스템 구축⑥

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage