|
该题目有以下几种情况可以考虑
1. 树是二叉搜索树，二叉搜索树的特点是根节点值大于所有左子树节点值，小于所有右子树节点值，则最低公共祖先即该节点值大于给定两个节点中的一个值，小于另外一个节点的值，go代码实现如下
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// 如果树是二叉搜索树
func getLastCommentNode(node1, node2, root *TreeNode) *TreeNode {
if nil == root || nil == node1 || nil == node2 {
return nil
}
if node1.Val < root.Val && node2.Val < root.Val {
return getLastCommentNode(node1, node2, root.Left)
}
if node1.Val > root.Val && node2.Val > root.Val {
return getLastCommentNode(node1, node2, root.Right)
}
return root
}
2. 树是普通二叉树，但节点有指向父节点的指针，则该问题转化为了求两个链表第一个相交的节点， go代码实现如下
type TreeNode1 struct {
Val int
Child []*TreeNode1
Parent *TreeNode1
}
// 带有父指针的普通树
func getLastCommentNode(node1, node2 *TreeNode1) *TreeNode1 {
len1 := getLengthToRoot(node1)
len2 := getLengthToRoot(node2)
if len1 > len2 {
for i := 0; i < len1 - len2; i++ {
node1 = node1.Parent
}
} else if len1 < len2 {
for i := 0; i < len2 - len1; i++ {
node2 = node2.Parent
}
}
for node1 != nil && node2 != nil {
if node1.Parent == node2.Parent {
return node1.Parent
}
node1 = node1.Parent
node2 = node2.Parent
}
return nil
}
func getLengthToRoot(node *TreeNode1) int {
if node == nil {
return 0
}
return 1 + getLengthToRoot(node.Parent)
}
3. 如果该树为普通树，且没有指向父节点的指针，则该问题可以转化成一下方式求解：a. 如果给定的两个节点都在当前节点同一个孩子的节点下面，则当前节点变成当前节点的孩子节点；b. 如果给定的两个节点在当前节点不同的孩子节点下面，则当前节点就是最低公共祖先，代码实现分为递归和非递归
递归实现（go）:
type TreeNode2 struct {
Val int
Child []*TreeNode2
}
// 普通树 递归实现
func getLastComentNode(node1, node2, root *TreeNode2) *TreeNode2 {
if root == nil {
return nil
}
found1, local1 := findNodeAndLocal(node1, root)
found2, local2 := findNodeAndLocal(node2, root)
if !found2 || !found1 {
return nil
}
if local2 == local1 {
return getLastComentNode(node1, node2, root.Child[local1])
}
return root
}
func findNode(node, root *TreeNode2) (bool) {
if root == nil {
return false
}
if root == node {
return true
}
found := false
for i := 0; i < len(root.Child) && !found; i++ {
found = findNode(node, root.Child[i])
}
return found
}
func findNodeAndLocal(node, root *TreeNode2) (bool, int) {
if root == nil {
return false, -1
}
found := false
local := -1
for i := 0; i < len(root.Child) && !found; i++ {
found = findNode(node, root.Child[i])
if found {
local = i
}
}
return found, local
}
非递归实现(go)：
//普通树 非递归实现
func getLastComentNode(node1, node2, root *TreeNode2) *TreeNode2 {
path1 := list.New()
path2 := list.New()
if nil == root || nil == node1 || nil == node2 {
return nil
}
getPath(node1, root, path1)
getPath(node2, root, path2)
var lastParentNode *TreeNode2
for path1.Front() != nil && path2.Front() != nil {
if path1.Front().Value == path2.Front().Value {
lastParentNode = path1.Front().Value.(*TreeNode2)
}
path1.Remove(path1.Front())
path2.Remove(path2.Front())
}
return lastParentNode
}
func getPath(node, root *TreeNode2, path *list.List) bool {
if node == root {
return true
}
path.PushBack(root)
found := false
for i:= 0; i < len(root.Child) && !found; i++ {
found = getPath(node, root.Child[i], path)
}
if !found {
path.Remove(path.Back())
}
return found
}
var c = &TreeNode2{Val: 3}
var d = &TreeNode2{Val: 4}
var e = &TreeNode2{Val: 5}
var b = &TreeNode2{Val: 2, Child: []*TreeNode2{d, e}}
var a = &TreeNode2{Val: 1, Child: []*TreeNode2{b, c}}
func TestTree(t *testing.T) {
temp := getLastComentNode(b, e, a)
fmt.Println(temp)
}
| 
转播
