【算法】求二叉树两个节点的最低公共祖先节点
2022/1/23 1:05:04
本文主要是介绍【算法】求二叉树两个节点的最低公共祖先节点,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
左程云算法与数据结构课 https://www.bilibili.com/video/BV13g41157hK?p=2&spm_id_from=pageDriver
题目
给定两个二叉树的节点node1和node2,找到他们的最低公共祖先节点。
题解
解法一
设置一个 HashMap 保存节点与该节点的父节点(设根节点的父节点为本身),然后再用一个集合 set1 保存 node1 的全部祖先节点,对node2往上求祖先节点,看是否在 set1 中,若在,则这个节点即为最低公共祖先节点。
//前提:node1和node2一定属于head为头的树 //返回node1和node2的最低公共祖先 public static Node lca(Node head, Node node1, Node node2) { HashMap<Node, Node> fatherMap = new HashMap<>(); //保存节点与该节点的父节点 fatherMap.put(head, head); //根节点的父节点为本身 process(head, fatherMap); //求所有节点的父节点 HashSet<Node> set1 = new HashSet<>(); //node1 的祖先节点集合 Node cur = node1; //求 node1 的祖先节点,并放入set1中 while (cur != fatherMap.get(cur)) { //回溯到根节点时停止 set1.add(cur); cur = fatherMap.get(cur); } set1.add(head); //求 node2 的祖先节点 cur = node2; while (!set1.contains(cur)) { //set1 中含该节点时停止 cur = fatherMap.get(cur); } //该节点即为最低公共祖先节点 return cur; } //递归求除根节点外所有节点的父节点,保存在 fatherMap 中 private static void process(Node head, HashMap<Node, Node> fatherMap) { if (head == null) { return; } fatherMap.put(head.left, head); fatherMap.put(head.right, head); process(head.left, fatherMap); process(head.right, fatherMap); }
解法二
在二叉树中有两种情况:
- 其中一个节点是另一个节点的子孙,则最低公共祖先节点是那个作为祖先的节点
- 两个节点不存在祖孙关系,则最低公共祖先节点是最近的公共祖先
试想这么一个递归操作:
- 基本事件是当一棵子树的头节点为 null 或 为 node1 或 node2 时,就返回这个头节点。
- 对左右子树作递归,获得左右子树的返回值。递归的返回值只有四种可能:null 、node1 、node2,两节点的最低公共祖先节点。
- 当左子树返回值不空,右子树返回值不空(即两节点分别落于左右子树上),返回头节点(该头节点即为最低公共祖先节点)。
- 当不满足左右子树返回值均不空这个条件时,若左子树返回值不空时返回该值(可能为node1 、node2,两节点的最低公共祖先节点),否则返回右子树的值(可能为null 、node1 、node2,两节点的最低公共祖先节点)。
在这个递归操作中,有以下情况:
-
若一棵子树不包含 node1 和 node2,那么它左右子树返回的值必定是 null,它往上返回的值也必定是 null;(a)
-
若一棵子树只包含 node1 和 node2 两者之一,这里假设包含的是node1,那么它往上返回的值是 node1;(b)
-
若一棵子树包含node1 和 node2 两者,
-
若 node1 和 node2 存在祖孙关系,那么node1 和 node2 只能存在于该树的左右子树其中一棵,假设 node1 为 祖先(node1是最低公共祖先节点),则该树的左右子树返回值必定是node1和null,根据递归操作的最后一条原则,不管是左子树返回值是node1 还是右子树返回值是node1,都能保证该树往上返回的是 node1。
-
若 node1 和 node2 不存在祖孙关系,分别落于它的左右子树中 ,根据(b),则左右子树返回的值分别是node1和node2,即满足左右子树返回值均不空,那么该子树往上返回的值是头节点。(c)
-
若 node1 和node2 不存在祖孙关系并且均落于该树的其中一棵子树上,假设均落于右子树上,则右子树的子树中必定存在这么一棵子树满足上面(c)条件,这棵子树返回值是头节点,也就是最低公共祖先节点,那么右子树最终返回的值也是该最低公共节点。左子树满足(a)条件,返回 null。故该树往上返回的值是最低公共祖先节点。
-
通过上面的刨析,就能写出下面优美的代码了。
public static Node lowestCommonAncestor(Node head, Node node1, Node node2) { if (head == null || head == node1 || head == node2) { //base case return head; } Node left = lowestCommonAncestor(head.left, node1, node2); Node right = lowestCommonAncestor(head.right, node1, node2); if (left != null && right != null) { return head; } return left != null ? left : right; }
这篇关于【算法】求二叉树两个节点的最低公共祖先节点的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)