LeetCode#236二叉树的最近公共祖先

题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]



 

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
 
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

简单分析

用栈保存p,q经历过的节点,然后从栈底开始即为它经历的从根开始到特定节点的遍历顺序,选出最近相同节点即为最近公共祖先。

代码

/**
 * 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:
    bool path(TreeNode *root,stack<TreeNode *> &s,TreeNode *p){
    if(root==NULL)
        return false;
    s.push(root);
    if(root->val==p->val)
    {
        return true;
    }
    bool flag = false;
    if(root->left!=NULL){
        flag = path(root->left,s,p);
    }
    if(!flag&&root->right!=NULL){
        flag = path(root->right,s,p);
    }
    if(!flag)
        s.pop();
    return flag;
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //若根为NULL,则返回NULL
        if(root == NULL)
            return NULL;
        //若有一个为NULL,则返回另一个节点即可
        if(p==NULL) return q;
        if(q==NULL) return p;

        //栈保存根到p,q分别经历的节点,然后选出最长前缀
        stack<TreeNode *> s1;
        stack<TreeNode *> s2;
        path(root,s1,p);
        path(root,s2,q);

        stack<TreeNode *> Stmp1;
        stack<TreeNode *> Stmp2;
        while(!s1.empty()){
            Stmp1.push(s1.top());
            s1.pop();
        }
        while(!s2.empty()){
            Stmp2.push(s2.top());
            s2.pop();
        }
        TreeNode *tmp = root;
        int size1 = Stmp1.size();
        int size2 = Stmp2.size();
        for(int i=0;i<size1&&i<size2;i++){
            int a = Stmp1.top()->val;
            int b = Stmp2.top()->val;

            if(a==b){
                tmp = Stmp1.top();
                Stmp1.pop();
                Stmp2.pop();
                continue;
            }
            else break;
        }
        return tmp;

}
};

LeetCode#236二叉树的最近公共祖先

LeetCode#236二叉树的最近公共祖先LeetCode#236二叉树的最近公共祖先 DUT_Walnut 发布了27 篇原创文章 · 获赞 4 · 访问量 1063 私信 关注
上一篇:236. 二叉树的最近公共祖先


下一篇:【树】236. 二叉树的最近公共祖先