关于leetcode算法:LCA问题二叉搜索树二叉树

55次阅读

共计 1512 个字符，预计需要花费 4 分钟才能阅读完成。

题意：
(1)所有节点的值都是惟一的。
(2)p、q 为不同节点且均存在于给定的二叉搜寻树中。

分 3 种状况：
(1) p、q 别离在 root 左右子树中。此时 root 即为最近公共先人
(2) p、q 都在左子树中，最近公共先人在左子树中，遍历左子树
(3) p、q 都在右子树中，遍历右子树

1、递归

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if((root->val - p->val) * (root->val - q->val) <= 0) return root;
        if(root->val > p->val) return lowestCommonAncestor(root->left, p, q);
        else return lowestCommonAncestor(root->right, p, q);
    }
};

2、迭代

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {while(1) {if((root->val - p->val) * (root->val - q->val) <= 0) return root;
            if(root->val > p->val) root = root->left;
            else root = root->right;
        }
        return root;
    }
};

后序遍历，当遇到节点 p 或 q 时返回，故依据返回值得出 pq 是否在子树中。
因为是后序遍历，故 第一次 碰到节点 p,q 在节点 root 的异侧时[包含 root== p 或 q 的状况]，节点 root 即为最近公共先人，则向上返回 root。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == nullptr || root == p || root == q) return root;
        TreeNode* l = lowestCommonAncestor(root->left, p, q);
        TreeNode* r = lowestCommonAncestor(root->right, p, q);
        if(!l && !r) return nullptr; //(1)
        if(!l) return r; //(3)
        if(!r) return l; //(4)
        return root; //(2) if(left != NULL and right != NULL)
    }
};

返回值：依据 left 和 right，可开展为四种状况；

当 left 和 right 同时为空：阐明 root 的左 / 右子树中都不蕴含 p,q，返回 null；
当 left 和 right 同时不为空：阐明 p,q 分列在 root 的异侧（别离在左 / 右子树），因而 root 为最近公共先人，返回 root；
当 left 为空，right 不为空：p,q 都不在 root 的左子树中，间接返回 right。具体可分为两种状况：
p,q 其中一个在 root 的右子树中，此时 right 指向 p（假如为 p）；
p,q 两节点都在 root 的右子树中，此时的 right 指向最近公共先人节点；
当 left 不为空，right 为空：与状况 3. 同理;