235/236-二叉搜索树的最近公共祖先

LeetCode 235. Lowest Common Ancestor of a Binary Search Tree

LeetCode-235

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).”

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

method

利用二叉搜索树的性质

• 如果root->val大于区间[p, q]，就往左边找
• 如果小于区间[p, q]，就往右边找
• 如果在区间里面，就肯定是最近公共祖先，直接返回

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root->val > p->val && root->val > q->val) 
        return lowestCommonAncestor(root->left, p, q);
    else if (root->val < p->val && root->val < q->val)
        return lowestCommonAncestor(root->right, p, q);
    return root;
}

---

LeetCode 236. Lowest Common Ancestor of a Binary Tree

LeetCode-236

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

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).”

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

method: 后序遍历

采用后序遍历，查找两个节点的位置，如果一个节点的左子树和右子树分别包含了p或q，那这个节点就是两个节点的最近公共祖先

属于有返回值的递归，但需要处理整棵树，因为我们要对返回值进行处理

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode *left = lowestCommonAncestor(root->left, p, q);
    TreeNode *right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;
    else if (!left && right) return right;
    else if (left && !right) return left;
    return nullptr;
}

后面的判断可以简写为

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode *left = lowestCommonAncestor(root->left, p, q);
    TreeNode *right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;
    return left ? left : right;
}

---

LeetCode 1740. 找到二叉树中的距离

给定一棵二叉树的根节点 root 以及两个整数 p 和 q ，返回该二叉树中值为 p 的结点与值为 q 的结点间的 距离 。

两个结点间的 距离 就是从一个结点到另一个结点的路径上边的数目。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 0
输出：3
解释：在 5 和 0 之间有 3 条边：5-3-1-0

method

先找最近公共祖先，再分别找祖先到两个节点的距离相加

TreeNode* findAncestor(TreeNode *root, int p, int q) {
    if (!root || root->val == p || root->val == q) return root;
    TreeNode *left = findAncestor(root->left, p, q);
    TreeNode *right = findAncestor(root->right, p, q);
    if (left && right) return root;
    return left ? left : right;
}
int getDist(TreeNode *root, int p) {
    if (!root) return -1;
    if (root->val == p) return 0;
    int left = getDist(root->left, p);
    int right = getDist(root->right, p);
    if (left != -1) return 1 + left;
    if (right != -1) return 1 + right;
    return -1;
}
int findDistance(TreeNode* root, int p, int q) {
    if (p == q) return 0;
    TreeNode *parent = findAncestor(root, p, q);
    return getDist(parent, p) + getDist(parent, q);
}