题解 | #二叉搜索树的最近公共祖先#(后序遍历-返回查找节点的值)

普通二叉树查找最近公共祖先

公共祖先 --- 后序遍历

递归左子树 和 递归右子树

如果找到指定需要的节点值p,q, 就返回该节点值，代表该子树有该值 如果没有找到在另一个子树中查找。 如果在两个子树中都找则代表为父亲节点直接返回

class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        return order(root, p, q)->val;
    }
    TreeNode* order(TreeNode* root, int p, int q){
        if(!root || root->val == p || root->val == q) return root;
        TreeNode* left = order(root->left, p, q);
        TreeNode* right = order(root->right, p, q);
        if(left == NULL) return right;
        if(right == NULL) return left;
        return root;
    }
};

二叉搜索树

增加节点判断条件 加快递归过程

class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        return order(root, p, q)->val;
    }
    TreeNode* order(TreeNode* root, int p, int q){
        if(!root || root->val == p || root->val == q) return root;
        TreeNode* left = order(root->left, p, q);
        TreeNode* right = order(root->right, p, q);
        if(root->val > p && root->val > q) return left;
        if(root->val < p && root->val < q) return right;
        return root;
    }
};

非递归

查找两个节点所有父亲节点 然后顺序比较最后一个相同的父亲节点即为公共祖先

class Solution {
public:
    /**
     
        
     */
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        int ans;
        vector<int> path1 = getPath(root, p);
        vector<int> path2 = getPath(root, q);
        for(int i = 0; i < path1.size() && i < path2.size(); i++){
            if(path1[i] == path2[i]) ans = path1[i];
            else break;
        }
        return ans;
    }
    vector<int> getPath(TreeNode* root, int target){
        TreeNode* node = root;
        vector<int> path;
        while(node){
            path.push_back(node->val);
            if(node->val == target) break;
            else if(node->val < target) node = node->right;
            else node = node->left;
        }
        return path;
    }
};