红色网站源码,源码下载网站源码,做班级相册网站的目的意义,成都网站建设四川推来客网络236. 二叉树的最近公共祖先
题目描述#xff1a; 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为#xff1a;“对于有根树 T 的两个节点 p、q#xff0c;最近公共祖先表示为一个节点 x#xff0c;满足 x 是 p、q 的祖先且 x 的…236. 二叉树的最近公共祖先
题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
考察重点DFS搜索两个节点当找到目标节点时返回1表示当前分支存在目标节点。回溯时当左右子树都返回1则认为是最近公共祖先
func findK1(res, root, p, q *TreeNode) int {var t1, t2 intif root nil { //搜索到叶节点返回0return 0}if root p || root q { //自己就是搜索的节点则还需要判断子节点中还有无另一个搜索节点如果有直接程序终止返回自己否则返回1表示这个分支有一个搜索节点if findK1(res, root.Left, p, q) 1 || findK1(res, root.Right, p, q) 1 {*res *root}return 1}t1 findK1(res, root.Left, p, q)t2 findK1(res, root.Right, p, q)if t1 1 t2 1 { //左右子树都有搜索节点的第一个节点证明自己就是他们的最近父节点直接wait.Done()返回自己*res *root} else if t1 1 || t2 1 { //左右子树一边有搜索节点返回1证明该分支有一个搜索节点return 1}return 0 //返回0表示这个分支无搜索节点
}
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {var res TreeNodefindK1(res, root, p, q)return res
}
