236. Lowest Common Ancestor of a Binary Tree

题目

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 p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

题意

求二叉树的LCA（最近公共祖先）

题解

由于是二叉树，而且对于pq来说，他们要么处在某个父节点的左右两边，要么就是p或q作为父节点，另外一个为其子节点。所以可以使用中选遍历的思路，如果左右子树包含pq，那么该节点就是最近祖先，如果某个节点本身等于p或q，且其子节点包含有p或q，则该节点为最佳祖先

代码

/**
 * Definition for TreeNode.
 * type TreeNode struct {
 *     Val int
 *     Left *ListNode
 *     Right *ListNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root==nil{
        return nil
    }
    
    
    _,lca := LCA(root,p,q)
    return lca
}

func LCA(root,p,q *TreeNode)(bool,*TreeNode){
    if root==nil{
        return false,nil
    }
    
    mid := false
    rl,node := LCA(root.Left,p,q)
    if node!=nil{
        return true,node
    }
    
    if root.Val==p.Val || root.Val==q.Val{
        mid = true
    }
    
    rr,node := LCA(root.Right,p,q)
    if node!=nil{
        return true,node
    }
    
    
    if mid&&(rl||rr){
        return true,root
    }    
    if rl&&rr{
        return true,root
    }
    
    return rl||rr||mid,nil
}

总结

这是针对二叉树的求法，算是比较简单，但是对于非二叉树的解法可能会更复杂。

• ← Previous Post
• Next Post →