面试题68:树中两个节点的最低公共祖先

题目

输入两个树节点，求它们的最低公共祖先

image.png

解题思路

• 若该树为二叉搜索树

1. 因为二叉搜索树是排过序的，位于左子树的节点都比父节点小，而位于右子树的节点都比父节点大，只需从根结点开始和两个输入的节点进行比较。
2. 如果当前节点的值比两个节点的值都大，那么最低的共同父节点一定在当前节点的左子树中，下一步遍历当前节点的左子树.
3. 如果当前节点的值比两个节点的值都小，那么最低的共同父节点一定在当前节点的右子树中，下一步遍历当前节点的右子树.
4. 这样在树中从上到下找到的第一个在两个输入节点的值之间的节点就是最低的公共祖先。

• 若该树是普通的树，且树中没有指向父节点的指针

1. 定义两个辅助的vector容器来保存从根结点到树中某一个节点的路径。
   2)采用先序遍历得到根结点到H的路径A->B->E->H,采用先序遍历得到根结点到F的路径A->B->D->F
2. 找到两个数据容器中最后一个相同的节点。

代码

• 普通树对应的代码

class Solution{
public:
    bool findPath(BinaryTreeNode *root,BinaryTreeNode* t,vector<BinaryTreeNode *>& v)
    {
        bool flag = false;
        //在vector中加入节点
        v.push_back(root);
        //如果找到节点，则flag = true，不再往下递归，开始返回
        if(root == t)
        {
            flag = true;
        }
        //左孩子不为NULL，且目前还没找到t，才能通过左子树递归
        if(root->left != NULL && flag == false)
        {
            flag = findPath(root->left,t,v);
        }
        //右孩子不为NULL，且已经查完左子树，在左子树中没找到t
        //才能沿着右子树递归查找，否则在左子树中找到t，则准备返回
        if(root->right != NULL && flag == false)
        {
            flag = findPath(root->right,t,v);
        }
        //此时数组中保存的是根结点到t的路径
        if(flag == false)
        {
            v.pop_back();
        }
        //cout << "每一轮flag:" << flag << endl;
        return flag;
    }

    BinaryTreeNode* lowestCommonParent(BinaryTreeNode* root,BinaryTreeNode* p,BinaryTreeNode* q)
    {
        if(root == NULL || p == NULL || q == NULL)
        {
            return NULL;
        }
        vector<BinaryTreeNode* > v1;
        vector<BinaryTreeNode* > v2;
        //第一步:找到根结点到两个节点的路径
        bool t1 = findPath(root,p,v1);
        cout << t1 << endl;
        bool t2 = findPath(root,q,v2);
        //t1 t2 都为true
        if(t1==true && t2 == true)
        {
            int i = 0,j = 0;
            BinaryTreeNode* tt;
            //逐步向后比较，找出最后一个相同的节点，即为输入结点的最低公共祖先
            while(i<v1.size() && j < v2.size() && v1[i] == v2[j])
            {
                tt = v1[i];
                cout << tt->val << endl;
                i++;
                j++;
            }
            return tt;
        }
        else //树中不存在p q
        {
            return NULL;
        }
    }

};

完整代码见Github