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

According to the : “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

_______3______       /              \    ___5__          ___1__   /      \        /      \   6      _2       0       8         /  \         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

 

hint：利用先序遍历分别获取root节点到目标节点的路径，然后比较两路径最长公布部分，就可以发现他们的LCA

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {        vector
     
       p_path, q_path;        vector
      
        path;        get_path(root, p, &path, &p_path);  // 获取root到p的节点路径        path.clear();        get_path(root, q, &path, &q_path);  // 获取root到q的节点路径        int len = min(p_path.size(), q_path.size());        int i = 0;        while (i < len && p_path[i] == q_path[i]) { // 找到第一个不同的节点，那么前一个节点就是LCD            ++i;        }                return p_path[i-1];    }        void get_path(TreeNode* root, TreeNode* target, vector
       
        * path, vector
        
         * target_path) {        if (!target_path->empty() && target_path->back() == target) {   // 如果已经找到了root到target节点的路径，那就直接不用搜            return ;        }                if (root == NULL) { // 空姐点直接不搜            return ;        }                path->push_back(root);  // 访问根节点，加入路径        if (path->back() == target) {   // 判断是否是到target节点            *target_path = *path;        }        get_path(root->left, target, path, target_path);    // 继续深搜左子树        get_path(root->right, target, path, target_path);   // 继续深搜右子树        path->pop_back();   // 回溯    }};
        
       
      
     

 

原来还有一道BST的LCA

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

According to the : “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

_______6______       /              \    ___2__          ___8__   /      \        /      \   0      _4       7       9         /  \         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

 

 

 hint：LCA->val 在 p->val与q->val之间

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {        int max_val = p->val, min_val = q->val;        if (max_val < min_val) {            swap(max_val, min_val);        }                TreeNode* cur = root;        while (cur != NULL) {            if (cur->val < min_val) {   // 若当前节点比两目标节点的值都小，需右移                cur = cur->right;            } else if (cur->val > max_val) {    // 若当前节点比两目标节点的值都大，需左移                cur = cur->left;            } else {                break;            }        }                return cur;    }};