1

读题

公共祖先LCA(T,p,q)表示一个结点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.

• 同样是子结构，可以从头到底，反复探索

• 没有递归，效率同样高

尝试提交错误的过程。

最复杂的递归思路摘录在这里

不仅仅dfs，2个递归混合的类型； 同层比较，错层比较混合类型；还有递归的出口都是难点；

• 1.这道题判断是否是子结构，主要看pRoot2和pRoot1的根节点的值是否一样，一样的话再同时递归，
• 2.【这一点有点难】判断left节点，如果pRoot2的左节点为null,则说明pRoot2的left节点满足条件。
• 3.【这一点更难】若pRoot2的节点不为null,并且pRoot1的left节点为null,或者说它们二者的值不一样，说明pRoot2不是pRoot1的子结构。
• 4.pRoot1和pRoot2的right节点和第2.3步一样的判断，当left和right同时成立，pRoot2才是pRoot1的子结构 5.【外部递归的出口】因为题目约定空树不是任意一个数的子结构，所以pRoot1和pRoot2都不能为空，这是返回true的前提条件

https://blog.nowcoder.net/n/6adb9fa3cb064b41a8b202c98b0b8f1a https://blog.nowcoder.net/n/fefb38a0bbb34ae88fadfaec3c6f7c9b

第一轮code

非递归的bl代码

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        
        
        // write code here
        
        //不用所谓的递归 尝试直接bl法
        //有一个根节点，还是有一个比较的过程；左边错一层，右边错一层，都有可能
        //边界值我也不知道
        if(!root){
            return 0;
        }
        
            int v;
        while(1){
            //这个容易错
            v = root->val;
            if(v <p && v<q){
                //root = root->left;
                root = root->right;
            }else if( v >p && v> q){
                //root = root->right;
                root = root->left;
            }else{
                //一边大，一边小
                break;
            }
        }
        return v;
    }
};