package top100liked

// https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/?envType=study-plan-v2&envId=top-100-liked

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

func buildTree(arr []*int) *TreeNode {
	if len(arr) == 0 || arr[0] == nil {
		return nil
	}

	root := &TreeNode{Val: *arr[0]}
	queue := []*TreeNode{root}
	i := 1

	for len(queue) > 0 && i < len(arr) {
		node := queue[0]
		queue = queue[1:]

		// 处理左孩子
		if i < len(arr) {
			if arr[i] != nil {
				node.Left = &TreeNode{Val: *arr[i]}
				queue = append(queue, node.Left)
			}
			i++
		}

		// 处理右孩子
		if i < len(arr) {
			if arr[i] != nil {
				node.Right = &TreeNode{Val: *arr[i]}
				queue = append(queue, node.Right)
			}
			i++
		}
	}

	return root
}

// // getParents 包括自身
// func getParents(root *TreeNode, target int) []*TreeNode {
// 	parents := []*TreeNode{}
// 	var res []*TreeNode
// 	var helper func(root *TreeNode) bool
// 	helper = func(root *TreeNode) bool {
// 		if root == nil {
// 			return false
// 		}
// 		if root.Val == target {
// 			res = append([]*TreeNode{}, parents...)
// 			res = append(res, root)
// 			return true
// 		}
// 		parents = append(parents, root)
// 		if helper(root.Left) {
// 			return true
// 		}
// 		if helper(root.Right) {
// 			return true
// 		}
// 		parents = parents[:len(parents)-1]
// 		return false
// 	}
// 	helper(root)
// 	return res
// }
// // 朴素解法，AC，但效率很低
// func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
// 	p1 := getParents(root, p.Val)
// 	p2 := getParents(root, q.Val)
// 	for i := len(p1) - 1; i >= 0; i-- {
// 		for j := len(p2) - 1; j >= 0; j-- {
// 			if p1[i].Val == p2[j].Val {
// 				return p1[i]
// 			}
// 		}
// 	}
// 	return nil
// }

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	var dfs func(*TreeNode) *TreeNode
	dfs = func(node *TreeNode) *TreeNode {
		if node == nil || node == p || node == q {
			return node
		}
		left := dfs(node.Left)
		right := dfs(node.Right)
		if left != nil && right != nil {
			return node
		}
		if left != nil {
			return left
		}
		return right
	}
	return dfs(root)
}