Hot 100 --- 二叉树的最近公共祖先

本文概览本文以LeetCode题目二叉树的最近公共祖先为例讲解后序遍历回溯汇总的思路重点说明三种返回值情况的处理一、题目二、题目分析题目要求给定二叉树根节点root以及两个节点p和q找到它们的最近公共祖先最近公共祖先的定义设节点root为节点p、q的某公共祖先若其左子节点root.left和右子节点root.right都不是p、q的公共祖先则称root是最近的公共祖先根据这个定义判断一个节点是不是最近公共祖先就要看它的左右子节点是不是公共祖先——如果左右子节点都不是公共祖先那当前节点就是最近公共祖先。最典型的情况就是p和q分别位于当前节点的左右两侧3 / \ 5 1 ← 3 是最近公共祖先p5 在左q1 在右 / \ \ 6 2 8所以核心思路就是后序遍历 回溯汇总。后序遍历先看左右子树再把左右子树的结果汇总到当前节点做判断思路概览Java 实现代码如下publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){returndfs(root,p,q);}privateTreeNodedfs(TreeNodenode,TreeNodep,TreeNodeq){// 如果当前节点为空返回nullif(nodenull){returnnull;}// 如果当前节点是p或q返回当前节点if(nodep||nodeq){returnnode;}// 递归搜索左子树TreeNodeleftdfs(node.left,p,q);// 递归搜索右子树TreeNoderightdfs(node.right,p,q);// 如果左子树和右子树都返回了非null值说明当前节点是最近公共祖先if(left!nullright!null){returnnode;}// 如果左子树或右子树返回了非null值说明最近公共祖先在该子树中returnleft!null?left:right;}思路简要说明整体是后序遍历 回溯汇总递归出口当前节点为空返回 null当前节点就是p或q直接返回自身后序遍历先递归左子树、再递归右子树拿到left和right两个返回值三种情况汇总left和right都不为 null →p、q分别在两侧当前节点就是最近公共祖先left和right只有一个不为 null → 把这个非 null 的值往上返回让上层节点继续判断left和right都为 null → 当前子树没找到返回 null核心就是每一步都把子树里找到了什么往上传让上层节点做判断三、思路详解第一步为什么是后序遍历要判断一个节点是不是最近公共祖先必须先知道它的左子树和右子树里有没有p和q。也就是说先处理左右子树再处理当前节点——这正是后序遍历左→右→根的顺序3 / \ 5 1 后序遍历顺序5 → 1 → 3 遍历到 3 时已经知道左子树找到了 5右子树找到了 1 → 3 就是最近公共祖先如果是前序遍历根→左→右到了 3 还没遍历左右子树根本不知道下面有没有p、q没法判断第二步递归的两个出口递归函数dfs(node, p, q)的作用是在以node为根的子树中查找p和q返回找到的节点或最近公共祖先出口 1node null遍历到空节点说明走到底了没找到返回 null出口 2node p或node q当前节点本身就是p或q直接返回自身。这里有一个关键点一旦命中就直接返回不再往下递归为什么不往下递归因为p或q已经找到了它下面的子树再找也没意义。另一个节点只可能有两种位置在它的子树里那p或q自己就是最近公共祖先祖先可以包含自己不在它的子树里那当前节点只是一个普通的目标节点上层的其他分支会找到另一个最后由上层汇总判断不管哪种情况当前节点只需要把自己返回给父节点就够了不需要往下递归第三步左右子树返回值的三种情况递归完左右子树后拿到left和right两个返回值。这两个值有三种组合每种对应一种情况情况 1left ! null right ! null两边都不为空说明左子树找到了一个p或q右子树也找到了另一个。此时当前节点就是最近公共祖先——p和q分别在它的左右两侧3 / \ 5 1 ← left5, right13 是最近公共祖先 / \ \ 6 2 8返回当前节点node情况 2left和right只有一个不为 null此时有两种子情况但对代码来说处理方式完全一样子情况 A最近公共祖先就在这个非 null 的子树里现在还没走到那一步需要把这个非 null 的值继续往上传递让上层节点去判断子情况 B找到的就是p或q本身另一个节点在它的子树下面所以p或q自己就是最近公共祖先不管是哪种子情况处理方式都是把非 null 的那个值往上返回子情况A示例最近祖先在子树深处往上传递 3 / \ 5 null ← 5 子树里找到了 p、q最近祖先是 5 / \ 6 2 ← 5 的 left6 不为nullright2 不为null → 5 是最近祖先 ← 3 的 left5返回的最近祖先rightnull → 把 5 往上传 子情况B示例p 或 q 自己就是最近祖先 3 / \ 5 1 / \ 6 2 ← p5, q2q 在 p 的子树里 ← 遍历到 5 时直接命中 p返回 5 ← 3 的 left5rightnull → 把 5 往上传5 就是最近祖先情况 3left和right都为 null说明左右子树都没找到p或q当前节点的子树里没有目标返回 nullreturnleft!null?left:right;// 如果 left 不为 null 返回 left否则返回 right// left 和 right 都为 null 时返回 right也是 null// left 和 right 只有一个不为 null 时返回那个非 null 的// left 和 right 都不为 null 时上面已经 return 了走不到这里这一行代码同时处理了情况 2 和情况 3很简洁第四步完整执行过程以这棵树为例3 / \ 5 1 / \ \ 6 2 8下面用三个例子分别演示三种情况。核心要盯住每个节点递归后拿到的left和right——左右子树返回了什么决定了当前节点怎么处理例1p 5q 1p、q 分别在根的左右两侧初始从根节点 3 开始访问节点 3当前路径3不是 p 也不是 q递归左右子树访问节点 5当前路径3→5命中 p5直接返回 5不再往下递归→ left 5访问节点 1当前路径3→1命中 q1直接返回 1不再往下递归→ right 1回到节点 3left5 不为 nullright1 不为 null → 3 就是最近公共祖先返回 3结果最近公共祖先是 3例2p 5q 2q 在 p 的子树里访问节点 3当前路径3不是 p 也不是 q递归左右子树访问节点 5当前路径3→5命中 p5直接返回 5不再往下递归2 虽然在 5 的子树里但命中后不往下找→ left 5访问节点 1当前路径3→1不是 p 也不是 q递归左右子树访问节点 null1 的左子树空节点返回 null→ left null访问节点 8当前路径3→1→8不是 p 也不是 q左右子树都是 null返回 null→ right null回到节点 1leftnullrightnull → 返回 null回到节点 3left5 不为 nullrightnull → 把 5 往上传返回 5结果最近公共祖先是 5q2 在 p5 的子树里p 自己就是最近祖先例3p 6q 2都在左子树最近祖先在深处访问节点 3当前路径3不是 p 也不是 q递归左右子树访问节点 5当前路径3→5不是 p 也不是 q递归左右子树访问节点 6当前路径3→5→6命中 p6直接返回 6→ left 6访问节点 2当前路径3→5→2命中 q2直接返回 2→ right 2回到节点 5left6 不为 nullright2 不为 null → 5 就是最近公共祖先返回 5→ 节点 3 的 left 5访问节点 1当前路径3→1不是 p 也不是 q递归左右子树左子树 null右子树 8 也不是 p、q → leftnullrightnull → 返回 null→ 节点 3 的 right null回到节点 3left5 不为 nullrightnull → 把 5 往上传返回 5结果最近公共祖先是 56 和 2 分别在 5 的左右两侧三个例子的共性例1左右子树都返回非 null → 当前节点就是最近祖先例2、例3只有一边返回非 null → 把这个非 null 的值往上传递最终传到根节点的就是答案不管最近祖先在哪个位置它一定是第一次出现 left 和 right 都不为 null的那个节点找到后就会一路被往上传第五步回溯汇总的本质整个过程其实就是回溯汇总每个节点把左右子树的查找结果汇总到一起做一次判断然后把结果往上传左右都找到了 → 当前节点就是最近祖先把自己往上返回只有一边找到了 → 把那一边的结果往上返回让上层继续判断两边都没找到 → 返回 null告诉上层这里没有最终结果会一层一层传递回根节点根节点拿到的就是最终答案这种后序遍历先拿到子树结果再在当前节点汇总的模式是二叉树问题中很常见的一种思路适用于需要综合左右子树信息来做判断的场景复杂度分析时间复杂度O(n)每个节点最多遍历一次空间复杂度O(h)递归栈深度等于树的高度最坏情况 O(n)