题解 | #二叉搜索树的最近公共祖先#

package main

// import "fmt"
import . "nc_tools"

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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @param p int整型
 * @param q int整型
 * @return int整型
 */
func lowestCommonAncestor(root *TreeNode, p int, q int) int {
	// write code here
	var s1, s2 []int
	var flag bool
	var dfs func(*TreeNode, int, []int) []int
	dfs = func(root *TreeNode, target int, path []int) []int {
		if flag || root == nil {
			return path
		}
		path = append(path, root.Val)
		if target == root.Val {
			flag = true
			return path
		}
		if root.Val > target {
			path = dfs(root.Left, target, path)
			if flag {
				return path
			}
		} else {
			path = dfs(root.Right, target, path)
			if flag {
				return path
			}
		}
        if len(path) > 0 {
			path = path[:len(path)-1]
		}
        return path
	}
    s1 = dfs(root, p, s1)
    //  fmt.Println(s1)
    flag = false
    s2 = dfs(root, q, s2)
    //  fmt.Println(s2)
    var res int
    for i := 0; i < len(s1); i++ {
        if i < len(s2) && s1[i] == s2[i] {
            res = s1[i]
        } else {
            return res
        }
    }
    return res

}