当前位置:网站首页>Finding the nearest common ancestor of binary search tree by recursion
Finding the nearest common ancestor of binary search tree by recursion
2022-07-06 00:50:00 【Hydrion-Qlz】
235. The nearest common ancestor of a binary search tree
difficulty : Simple
Given a binary search tree , Find the nearest common ancestor of the two specified nodes in the tree .
Baidu Encyclopedia The definition of the most recent common ancestor in is :“ For a tree T Two nodes of p、q, Recently, the common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible ( A node can also be its own ancestor ).”
Ideas
This problem must be used well BST Properties of trees !
There are three situations
- Both nodes are smaller than the current node , Are all on the left subtree of the current node
- Both nodes are larger than the current node , Are all on the right subtree of the current node
- One is larger than the current node ( Or equal to ), One is smaller than the current node ( Or equal to ), Then the current node is the nearest common ancestor of the two nodes
Using recursion is easy
package cn.edu.xjtu.carlWay.tree.commonAncestorBST;
import cn.edu.xjtu.Util.TreeNode.TreeNode;
/** * 235. The nearest common ancestor of a binary search tree * Given a binary search tree , Find the nearest common ancestor of the two specified nodes in the tree . * <p> * In Baidu Encyclopedia, the most recent definition of public ancestor is :“ For a tree T Two nodes of p、q, Recently, the common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible ( A node can also be its own ancestor ). * <p> * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/ */
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// case 1
if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
// case 2
if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
// case 3
return root;
}
}
边栏推荐
- KDD 2022 | EEG AI helps diagnose epilepsy
- Spark AQE
- Construction plan of Zhuhai food physical and chemical testing laboratory
- 激动人心,2022开放原子全球开源峰会报名火热开启
- 程序员成长第九篇:真实项目中的注意事项
- VSphere implements virtual machine migration
- Intranet Security Learning (V) -- domain horizontal: SPN & RDP & Cobalt strike
- A preliminary study of geojson
- 如何制作自己的机器人
- Folding and sinking sand -- weekly record of ETF
猜你喜欢
XML配置文件
毕设-基于SSM高校学生社团管理系统
Intensive learning weekly, issue 52: depth cuprl, distspectrl & double deep q-network
[groovy] JSON string deserialization (use jsonslurper to deserialize JSON strings | construct related classes according to the map set)
MCU通过UART实现OTA在线升级流程
XML Configuration File
Opencv classic 100 questions
Cf:d. insert a progression [about the insert in the array + the nature of absolute value + greedy top-down]
Leetcode:20220213 week race (less bugs, top 10% 555)
Common API classes and exception systems
随机推荐
NLP text processing: lemma [English] [put the deformation of various types of words into one form] [wet- > go; are- > be]
免费的聊天机器人API
Natural language processing (NLP) - third party Library (Toolkit):allenlp [library for building various NLP models; based on pytorch]
Spark AQE
VSphere implements virtual machine migration
The detailed page returns to the list and retains the original position of the scroll bar
The population logic of the request to read product data on the sap Spartacus home page
Spark DF adds a column
Starting from 1.5, build a micro Service Framework - call chain tracking traceid
Model analysis of establishment time and holding time
cf:H. Maximal AND【位运算练习 + k次操作 + 最大And】
Illustrated network: the principle behind TCP three-time handshake, why can't two-time handshake?
[groovy] XML serialization (use markupbuilder to generate XML data | create sub tags under tag closures | use markupbuilderhelper to add XML comments)
KDD 2022 | EEG AI helps diagnose epilepsy
Pointer - character pointer
Installation and use of esxi
Study diary: February 13, 2022
How to use the flutter framework to develop and run small programs
Classic CTF topic about FTP protocol
95后CV工程师晒出工资单,狠补了这个,真香...