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

package main
// import "fmt"
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 {
    // write code here
    var s1, s2 []int
    var end bool
    var dfs func(*TreeNode, int, []int) []int
    dfs = func(root *TreeNode, target int, path []int) []int {
        if root == nil || end {
            return path
        }
        path = append(path, root.Val)
        if root.Val == target {
            end = true
            return path
        }
        path = dfs(root.Left, target, path)
        path = dfs(root.Right, target, path)
        if end {
            return path
        }
        if len(path) > 0 {
            path = path[:len(path)-1]
        }
        return path
    }
    s1 = dfs(root, o1, s1)
    end = false
    s2 = dfs(root, o2, s2)
    var l int
    if len(s1) < len(s2) {
        l = len(s1)
    } else {
        l = len(s2)
    }
    var res int

	for i := 0; i < l; i++ {
		if s1[i] != s2[i] {
			break
		}
		res = s1[i]
	}

	return res
}

暴力解法：深度优先搜索，分别找出两个val的路径，再进行比较