235. Lowest Common Ancestor of a BST
问题
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
DFS搜索,如果当前节点为null,则返回null。
如果当前节点小于p和q的值,则递归其左子节点。
反之递归其右子节点。
如果当前节点在p与q之间,则返回当前节点。
该节点是p与q的Lowest Common Ancestor。
1 | /** |
235. Lowest Common Ancestor of a BST
https://xuanhe95.github.io/2022/04/16/235-Lowest-Common-Ancestor-of-a-BST/