# 2020-08-30：裸写算法：二叉树两个节点的最近公共祖先。

2020-11-06 21:50:41

1.递归

2.存储父节点

3.迭代

``````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("存储父节点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是叶子节点
return nil
}
//左节点搜索不到了，说明右节点是根节点
if left == nil {
return right
}
//右节点搜索不到了，说明左节点是根节点
if right == nil {
return left
}
//左右都有，说明root就是根节点
return root
}

//存储父节点
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的访问状态
stackvisited = append(stackvisited, 0) //0未访问 1左节点已经访问 2右节点已访问

var cur *TreeNode = nil
var ret *TreeNode = nil
for len(stack) > 0 {
cur = nil
if stackvisited[len(stackvisited)-1] == 0 { //未访问
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 { //左节点已访问
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 { //右节点已访问
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
}``````

https://my.oschina.net/u/4553401/blog/4536633