自底向上怎么办回溯啊都是递归从上向下和从下向上有什么区别代码可视化自顶向下处理(root); go(root-left); go(root-right);自底向上go(root-left); go(root-right); 处理(root);如果找到一个节点发现左子树出现结点p右子树出现节点q或者 左子树出现结点q右子树出现节点p那么该节点就是节点p和q的最近公共祖先。遇见p就回溯遇见q也回溯如果返回值两边同时不为空那这个节点就是要找的节点。遇到 q 或者 p 就返回这样也包含了 q 或者 p 本身就是 公共祖先的情况。递归三部曲确定递归函数返回值以及参数需要递归函数返回值来告诉我们是否找到节点q或者p那么返回值为bool类型就可以了。但我们还要返回最近公共节点可以利用上题目中返回值是TreeNode * 那么如果遇到p或者q就把q或者p返回返回值不为空就说明找到了q或者p。代码如下TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)确定终止条件遇到空的话因为树都是空了所以返回空。那么我们来说一说如果 root q或者 root p说明找到 q p 则将其返回这个返回值后面在中节点的处理过程中会用到那么中节点的处理逻辑下面讲解。代码如下if (root q || root p || root NULL) return root;确定单层递归逻辑虽然我的递归函数有返回值比如返回找到的节点指针但我不能像查字典那样找到就立刻返回。我必须先把左子树的返回值看看再把右子树的返回值看看根据两边的情况综合判断最后再决定返回什么。举个“有返回值但依然全遍历”的代码骨架LCATreeNode* find(TreeNode* root, TreeNode* p, TreeNode* q) { if (!root || root p || root q) return root; // ① 我先去左边找并不直接返回 TreeNode* left find(root-left, p, q); // ② 我再必须去右边找这就是全遍历 TreeNode* right find(root-right, p, q); // ③ 走完两边了我才根据结果做决策 if (left right) return root; // 两边都找到了当前就是祖先 return left ? left : right; // 哪边找到了就返回哪边 }这里虽然有返回值TreeNode*但你看第 ① 和第 ② 步它并没有在第 ① 步找到东西后就return而是先存起来继续去执行第 ② 步。这就强制程序把左、右子树全部遍历完。看逻辑就看代码随想录吧。我觉得可以把这道题背下来不难。但是现在其实我已经理解了就是1.先判断一下返回什么例如上图65null都要返回。2.递归找left和right3.分别判断left和right找到了返回root没找到返回什么的情况。那如果是二叉搜索树呢特别简单不用使用回溯二叉搜索树自带方向性可以方便的从上向下查找目标区间遇到目标区间内的节点直接返回。迭代即可。都大于就去左边都小于就去右边要么就返回root出循环了就返回nullclass Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { while(root){ if(root-valq-valroot-valp-val){ rootroot-left; } else if(root-valq-valroot-valp-val){//这里要用else如果只用if的话在一环root变化之后还会在这里再判断一次进入第一个 ifroot 被更新为左孩子。然后程序继续执行第二个 if此时 root 已经改变可能会错误地进入第二个分支 rootroot-right; } else return root; } return NULL; } };