摘要：package mainimport ("fmt""testing")// TreeNode represents a node in a binary treetype TreeNode struct {Val intLeft *TreeNodeRight
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
一开始有点绕，后来想明白了，代码如下很简单：
package mainimport ("fmt""testing")// TreeNode represents a node in a binary treetype TreeNode struct {Val intLeft *TreeNodeRight *TreeNode}func travelSal(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode {if root == nil {return nil}if root == p || root == q {return root}left := travelSal(root.Left, p, q)right := travelSal(root.Right, p, q)if left != nil && right != nil {return root}if left != nil {return left} else {return right}}func TestGrandpa(t *testing.T) {// 构建一个示例二叉树p := &TreeNode{Val: 4,}q := &TreeNode{Val: 6,}root := &TreeNode{Val: 5,Left: &TreeNode{Val: 3,Left: &TreeNode{Val: 2,},Right: p,},Right: &TreeNode{Val: 8,Left: q,Right: &TreeNode{Val: 9,},},}lastFather := travelSal(root, p, q)fmt.Println("lastFather:", lastFather.Val)}来源：风林火山
免责声明：本站系转载，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与本站联系，我们将在第一时间删除内容!
