PHP 求解二叉树 - 二叉搜索树的最近公共祖先
source link: http://hxd.best/2020/09/27/PHP-求解二叉树-二叉搜索树的最近公共祖先/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree
解题思路
这题让求二叉搜索树的最近公共祖先，而二叉搜索树的特点就是左子树的所有节点都小于当前节点，右子树的所有节点都大于当前节点，并且每棵子树都具有上述特点，所以这题就好办了，从更节点开始遍历
- 如果两个节点值都小于根节点，说明他们都在根节点的左子树上，我们往左子树上找
- 如果两个节点值都大于根节点，说明他们都在根节点的右子树上，我们往右子树上找
- 如果一个节点值大于根节点，一个节点值小于根节点，说明他们他们一个在根节点的左子树上一个在根节点的右子树上，那么根节点就是他们的最近公共祖先节点。
作者：sdwwld 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/solution/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-3c/ 来源：力扣（LeetCode）
代码
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class Solution {
/**
* @param TreeNode $root
* @param TreeNode $p
* @param TreeNode $q
* @return TreeNode
*/
function lowestCommonAncestor($root, $p, $q) {
//如果根节点和p,q的差相乘是正数，说明这两个差值要么都是正数要么都是负数，也就是说
//他们肯定都位于根节点的同一侧，就继续往下找
while (($root->val - $p->val) * ($root->val - $q->val) > 0)
$root = $p->val < $root->val ? $root->left : $root->right;
//如果相乘的结果是负数，说明p和q位于根节点的两侧，如果等于0，说明至少有一个就是根节点
return $root;
}
}
二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
(递归) O(n)
当我们用递归去做这个题时不要被题目误导，应该要明确一点 这个函数的功能有三个：给定两个节点 pp 和 qq
如果 pp 和 qq 都存在，则返回它们的公共祖先； 如果只存在一个，则返回存在的一个； 如果 pp 和 qq 都不存在，则返回NULL 本题说给定的两个节点都存在，那自然还是能用上面的函数来解决
具体思路： （1） 如果当前结点 rootroot 等于 NULL，则直接返回 NULL （2） 如果 rootroot 等于 pp 或者 qq ，那这棵树一定返回 pp 或者 qq （3） 然后递归左右子树，因为是递归，使用函数后可认为左右子树已经算出结果，用 leftleft 和 rightright 表示 （4） 此时若leftleft为空，那最终结果只要看 rightright；若 rightright 为空，那最终结果只要看 leftleft （5） 如果 leftleft 和 rightright 都非空，因为只给了 pp 和 qq 两个结点，都非空，说明一边一个，因此 rootroot 是他们的最近公共祖先 （6） 如果 leftleft 和 rightright 都为空，则返回空（其实已经包含在前面的情况中了）
时间复杂度是 O(n)：每个结点最多遍历一次或用主定理，空间复杂度是 O(n)：需要系统栈空间
作者：Wilson79 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/c-jing-dian-di-gui-si-lu-fei-chang-hao-li-jie-shi-/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
代码
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class Solution {
/**
* @param TreeNode $root
* @param TreeNode $p
* @param TreeNode $q
* @return TreeNode
*/
function lowestCommonAncestor($root, $p, $q) {
if ($root == null || $root == $p || $root == $q)
return $root;
$left = $this->lowestCommonAncestor($root->left, $p, $q);
$right = $this->lowestCommonAncestor($root->right, $p, $q);
//如果left为空，说明这两个节点在cur结点的右子树上，我们只需要返回右子树查找的结果即可
if ($left == null)
return $right;
//同上
if ($right == null)
return $left;
//如果left和right都不为空，说明这两个节点一个在cur的左子树上一个在cur的右子树上，
//我们只需要返回cur结点即可。
if ($left && $right) {
return $root;
}
return null;
}
}
参考链接
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK