题解 | #在二叉树中找到两个节点的最近公共祖先#

package main

import . "nc_tools"

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 *
 * @param root TreeNode类
 * @param o1 int整型
 * @param o2 int整型
 * @return int整型
 */
func lowestCommonAncestor(root *TreeNode, o1 int, o2 int) int {
	sta1 := make([]int, 10)
	sta2 := make([]int, 10)
	sta1, top1 := find(root, o1, sta1, 0)
	sta2, top2 := find(root, o2, sta2, 0)
	a := sta1
	b := sta2
	for i, j := top1-1, top2-1; ; {
		i--
		j--
		if i < 0 && j < 0 {
			return -1
		}
		if i < 0 {
			i = top2 - 1
			a = sta2
		}
		if j < 0 {
			j = top1 - 1
			b = sta1
		}
		if a[i] == b[j] {
			return a[i]
		}
	}
	return -1
}

func find(root *TreeNode, o int, sta []int, top int) (st []int, t int) {
	if root == nil {
		return sta, -1
	}
	if len(sta) <= top {
		sta = append(sta, root.Val)
	} else {
		sta[top] = root.Val
	}
	top++
	if root.Val == o {
		return sta, top
	}
	sta, left := find(root.Left, o, sta, top)
	if left >= 0 {
		return sta, left
	}
	return find(root.Right, o, sta, top)
}