专栏首页学习日记Golang Leetcode 235. Lowest Common Ancestor of a Binary Search Tree.go

Golang Leetcode 235. Lowest Common Ancestor of a Binary Search Tree.go

版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89043473

思路

寻找最近的公共祖先,当root非空时可以区分为三种情况:1)两个节点均在root的左子树,此时对root->left递归求解;2)两个节点均在root的右子树,此时对root->right递归求解;3)两个节点分别位于root的左右子树,此时LCA为root。

code

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

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {

	if root == nil {
		return nil
	}

	for root != nil {
		if p.Val > root.Val && q.Val > root.Val {
			root = root.Right
		} else if p.Val < root.Val && q.Val < root.Val {
			root = root.Left
		} else {
			return root
		}
	}
	return nil

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Golang Leetcode 687. Longest Univalue Path.go

    更多内容请移步我的repo:https://github.com/anakin/golang-leetcode

    anakinsun
  • Golang leetcode 513. Find Bottom Left Tree Value.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89175648

    anakinsun
  • Golang Leetcode 700. Search in a Binary Search Tree.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/arti...

    anakinsun
  • 【leetcode刷题】T112-验证二叉搜索树

    节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。

    木又AI帮
  • 958. 二叉树的完全性检验

    输入:[1,2,3,4,5,null,7] 输出:false 解释:值为 7 的结点没有尽可能靠向左侧

    程序员小王
  • linux基础命令介绍三:文件搜索及其它

    find是一个非常有效的工具,它可以遍历目标目录甚至整个文件系统来查找某些文件或目录:

    用户5030870
  • 如何使用CP / SCP / RSYNC在Linux中排除特定目录?

    对于任何系统管理员或一般Linux操作系统用户而言,在服务器之间执行文件复制操作都是一项常见任务。在将文件从一个系统复制到另一个系统时,由于某些特定原因,我们可...

    用户6543014
  • 14.4 exportfs命令

    exportfs命令 常用选项 -a 全部挂载或者全部卸载 -r 重新挂载 -u 卸载某一个目录 -v 显示共享目录 以下操作在服务端上 -vim /etc/e...

    运维小白
  • 二叉树高频题

    Given a binary tree, return the preorder traversal of its nodes' values.

    王脸小
  • BST & AVL 二分搜索树 & 平衡二叉树的实现原理

    本文完整的实现了基本的BST,由于注重的是逻辑和原理的实现,所以没有采用泛型。注意方法的访问修饰符。

    大学里的混子

扫码关注云+社区

领取腾讯云代金券