[Day32-04]-[二叉树] 二叉树的最近公共祖先

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出：3解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4输出：5解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

输入：root = [1,2], p = 1, q = 2输出：1

func TestLowestCommonAncestor(t *testing.T) {	var root = &TreeNode{		Val: 2,		Left: &TreeNode{			Val: 1,			Left: &TreeNode{				Val: 4,			},			Right: &TreeNode{				Val: 5,			},		},		Right: &TreeNode{			Val: 3,		},	}	// 题解：	// 这里需要采用后序遍历 LRD, 这样第一次出现公共节点一定是最近的公共节点	var dfs func(root, p, q *TreeNode) *TreeNode	dfs = func(root, p, q *TreeNode) *TreeNode {		if root == nil { // 递归终止条件			return nil		}		if root == p || root == q { // 只要找到了一个就得返回			return root		}		l := dfs(root.Left, p, q)		r := dfs(root.Right, p, q)		if l != nil && r != nil { // p,q一定是分散在root的左右的			return root		}		if l == nil { // 右侧找到了			return r		}		return l // 左侧找到了	}	res := dfs(root, root.Left.Left, root.Right)	t.Log(res)}