福哥答案2020-08-30：

1.遞歸
算法
左節(jié)點(diǎn)子函數(shù)返回值不空，右節(jié)點(diǎn)子函數(shù)返回值為空，返回左節(jié)點(diǎn)。
左節(jié)點(diǎn)子函數(shù)返回值為空，右節(jié)點(diǎn)子函數(shù)返回值不空，返回右節(jié)點(diǎn)。
左節(jié)點(diǎn)子函數(shù)返回值不空，右節(jié)點(diǎn)子函數(shù)返回值不空，返回當(dāng)前節(jié)點(diǎn)。
復(fù)雜度分析：
時(shí)間復(fù)雜度 O(N) ： 其中 N 為二叉樹(shù)節(jié)點(diǎn)數(shù)；最差情況下，需要遞歸遍歷樹(shù)的所有節(jié)點(diǎn)。
空間復(fù)雜度 O(N) ： 最差情況下，遞歸深度達(dá)到 N ，系統(tǒng)使用 O(N) 大小的額外空間。

2.存儲(chǔ)父節(jié)點(diǎn)
思路
我們可以用哈希表存儲(chǔ)所有節(jié)點(diǎn)的父節(jié)點(diǎn)，然后我們就可以利用節(jié)點(diǎn)的父節(jié)點(diǎn)信息從 p 結(jié)點(diǎn)開(kāi)始不斷往上跳，并記錄已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)，再?gòu)?q 節(jié)點(diǎn)開(kāi)始不斷往上跳，如果碰到已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)，那么這個(gè)節(jié)點(diǎn)就是我們要找的最近公共祖先。
算法
從根節(jié)點(diǎn)開(kāi)始遍歷整棵二叉樹(shù)，用哈希表記錄每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)指針。
從 p 節(jié)點(diǎn)開(kāi)始不斷往它的祖先移動(dòng)，并用數(shù)據(jù)結(jié)構(gòu)記錄已經(jīng)訪問(wèn)過(guò)的祖先節(jié)點(diǎn)。
同樣，我們?cè)購(gòu)?q 節(jié)點(diǎn)開(kāi)始不斷往它的祖先移動(dòng)，如果有祖先已經(jīng)被訪問(wèn)過(guò)，即意味著這是 p 和 q 的深度最深的公共祖先，即 LCA 節(jié)點(diǎn)。
復(fù)雜度分析
時(shí)間復(fù)雜度：O(N)，其中 N 是二叉樹(shù)的節(jié)點(diǎn)數(shù)。二叉樹(shù)的所有節(jié)點(diǎn)有且只會(huì)被訪問(wèn)一次，從 p 和 q 節(jié)點(diǎn)往上跳經(jīng)過(guò)的祖先節(jié)點(diǎn)個(gè)數(shù)不會(huì)超過(guò) N，因此總的時(shí)間復(fù)雜度為 O(N)。
空間復(fù)雜度：O(N)，其中 N 是二叉樹(shù)的節(jié)點(diǎn)數(shù)。遞歸調(diào)用的棧深度取決于二叉樹(shù)的高度，二叉樹(shù)最壞情況下為一條鏈，此時(shí)高度為 N，因此空間復(fù)雜度為 O(N)，哈希表存儲(chǔ)每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)也需要 O(N)的空間復(fù)雜度，因此最后總的空間復(fù)雜度為 O(N)。

3.迭代
思路
深度優(yōu)先遍歷，遍歷到兩個(gè)值，答案就出來(lái)了。
復(fù)雜度分析
時(shí)間復(fù)雜度 O(N) ： 其中 N 為二叉樹(shù)節(jié)點(diǎn)數(shù)；最差情況下，需要遞歸遍歷樹(shù)的所有節(jié)點(diǎn)。
空間復(fù)雜度 O(Level) ： Level是樹(shù)的最大深度。

代碼用go語(yǔ)言編寫(xiě)，如下：

package test35_lowestcommonancestor

import (
    "fmt"
    "testing"
)

//go test -v -test.run TestLowestCommonAncestor
func TestLowestCommonAncestor(t *testing.T) {
    root := &TreeNode{}
    root.Val = 3

    root.Left = &TreeNode{}
    root.Left.Val = 5
    root.Right = &TreeNode{}
    root.Right.Val = 1

    root.Right.Left = &TreeNode{}
    root.Right.Left.Val = 0
    root.Right.Right = &TreeNode{}
    root.Right.Right.Val = 8

    root.Left.Left = &TreeNode{}
    root.Left.Left.Val = 6
    root.Left.Right = &TreeNode{}
    root.Left.Right.Val = 2

    root.Left.Right.Left = &TreeNode{}
    root.Left.Right.Left.Val = 7
    root.Left.Right.Right = &TreeNode{}
    root.Left.Right.Right.Val = 4
    p := root.Right.Right
    q := root.Left.Right.Right

    fmt.Println("p = ", p)
    fmt.Println("q = ", q)
    ret := LowestCommonAncestor1(root, p, q)
    fmt.Println("遞歸ret = ", ret)
    ret = LowestCommonAncestor2(root, p, q)
    fmt.Println("存儲(chǔ)父節(jié)點(diǎn)ret = ", ret)
    ret = LowestCommonAncestor3(root, p, q)
    fmt.Println("迭代ret = ", ret)

}

//Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

//遞歸
func LowestCommonAncestor1(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }
    left := LowestCommonAncestor1(root.Left, p, q)
    right := LowestCommonAncestor1(root.Right, p, q)
    if left == nil && right == nil { //root是葉子節(jié)點(diǎn)
        return nil
    }
    //左節(jié)點(diǎn)搜索不到了，說(shuō)明右節(jié)點(diǎn)是根節(jié)點(diǎn)
    if left == nil {
        return right
    }
    //右節(jié)點(diǎn)搜索不到了，說(shuō)明左節(jié)點(diǎn)是根節(jié)點(diǎn)
    if right == nil {
        return left
    }
    //左右都有，說(shuō)明root就是根節(jié)點(diǎn)
    return root
}

//存儲(chǔ)父節(jié)點(diǎn)
func LowestCommonAncestor2(root, p, q *TreeNode) *TreeNode {
    parent := map[int]*TreeNode{}
    visited := map[int]bool{}

    var dfs func(*TreeNode)
    dfs = func(r *TreeNode) {
        if r == nil {
            return
        }
        if r.Left != nil {
            parent[r.Left.Val] = r
            dfs(r.Left)
        }
        if r.Right != nil {
            parent[r.Right.Val] = r
            dfs(r.Right)
        }
    }
    dfs(root)

    for p != nil {
        visited[p.Val] = true
        p = parent[p.Val]
    }
    for q != nil {
        if visited[q.Val] {
            return q
        }
        q = parent[q.Val]
    }

    return nil
}

//迭代
func LowestCommonAncestor3(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }
    //push根
    stack := make([]*TreeNode, 0)
    stack = append(stack, root)
    stackvisited := make([]int, 0)         //記錄stack的訪問(wèn)狀態(tài)
    stackvisited = append(stackvisited, 0) //0未訪問(wèn) 1左節(jié)點(diǎn)已經(jīng)訪問(wèn) 2右節(jié)點(diǎn)已訪問(wèn)

    var cur *TreeNode = nil
    var ret *TreeNode = nil
    for len(stack) > 0 {
        cur = nil
        if stackvisited[len(stackvisited)-1] == 0 { //未訪問(wèn)
            stackvisited[len(stackvisited)-1] = 1
            if stack[len(stack)-1].Left != nil {
                stack = append(stack, stack[len(stack)-1].Left)
                stackvisited = append(stackvisited, 0)
                cur = stack[len(stack)-1]
            }
        } else if stackvisited[len(stackvisited)-1] == 1 { //左節(jié)點(diǎn)已訪問(wèn)
            stackvisited[len(stackvisited)-1] = 2
            if stack[len(stack)-1].Right != nil {
                stack = append(stack, stack[len(stack)-1].Right)
                stackvisited = append(stackvisited, 0)
                cur = stack[len(stack)-1]
            }
        } else { //右節(jié)點(diǎn)已訪問(wèn)
            if ret != nil {
                if stack[len(stack)-1] == ret {
                    ret = stack[len(stack)-2]
                }
            }
            //pop
            stack = stack[0 : len(stack)-1]
            stackvisited = stackvisited[0 : len(stackvisited)-1]
        }
        if cur != nil {
            if cur == p {
                if ret != nil { //第二次
                    break
                } else { //第一次
                    ret = cur
                }
            }
            if cur == q {
                if ret != nil { //第二次
                    break
                } else { //第一次
                    ret = cur
                }
            }
        }
    }

    return ret
}

敲 go test -v -test.run TestLowestCommonAncestor 命令，執(zhí)行結(jié)果如下：

image.png

評(píng)論