[Golang][Leetcode][BinaryTree]刷題系列-236-Lowest Common Ancestor of a Binary Tree

Steven included in Leetcode Golang

2021-09-10 591 words 3 minutes

/leetcode236_binarytree/golang_leetcode.png

Contents

236. Lowest Common Ancestor of a Binary Tree

Level : Medium

原題連結 : Click

題目 :

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).”

Example :

Note

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2 Output: 1

解題思路 :

這題需要我們找出兩nodes的最低共同祖先
以下提供兩個解題思路:
1. 第一種(我最一開始想到的): 先做一次preorder並將整棵樹存進stack，在從頭部開始找 p or q 其中一個node，若先找到 p 我就設定target為 q，反之則設target為 p ，並擷取頭部到 p(or q)的slice做為新的stack，這樣做的目的是因為preorder的關係，p 跟 q 的共同祖先們都在此新的stack中，於是我們再把此stack裡的node從尾部一個一個push出來(因為越尾部越接近當初找到的 p(or q))，並以他們為root做preorder找出是否是target的祖先，第一個符合此條件的node便是 p, q的最低共同祖先
2. 第二種‵: 是直接將樹分成兩半做判斷，寫法也很直觀，若找到 p 或 q 就直接回傳該node，若是沒找到就回傳nil，分成兩邊就可以做篩檢，若回傳為nil就直接忽略了，往有找到的那邊繼續往下找，直到兩邊都有找到，那代表該node便是他們的最低共同祖先

Recursive-1解法

time complexity: O(n^2) , space complexity: O(n)

Runtime: 4 ms, faster than 99.71% of Go online submissions for Lowest Common Ancestor of a Binary Tree.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
 
    var stack []*TreeNode
    
    preorder(root, &stack)
    
    var tar *TreeNode
    
    for i, v := range stack {
        
        if v == p {
            tar = q
            stack = stack[:i+1]
            break
        }
        
        if v == q {
            tar = p
            stack = stack[:i+1]
            break
        }    
    }
    
    res := false
    
    for i := len(stack)-1; i >= 0; i-- {
        
        findpOrq(stack[i], tar.Val, &res)
        if res {
            return stack[i]
        }
    }
    
    return root
    
}

func preorder(node *TreeNode, stack *[]*TreeNode) {
    
    
    if node == nil {
        return 
    }
    
    *stack = append(*stack, node)
    
    preorder(node.Left, stack)
    
    preorder(node.Right, stack)
}


func findpOrq(node *TreeNode, tar int, res *bool) {
    
    if node == nil  {
        return
    }
    
    if node.Val == tar {
        *res = true
    }
    
    findpOrq(node.Left, tar, res) 
    
    findpOrq(node.Right, tar, res)
        
}

Recursive-2解法

time complexity: O(n) , space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    
    if root == nil {
        return root
    } 
    
    if root == p || root == q {
        return root
    }
    
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)

    if left != nil && right != nil {
        return root
    }
    
    if left != nil {
        return left
    }
    
    if right != nil {
        return right
    }
    
    return nil
    
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!