自主建站,护肤品主题网站怎么做,广东建设集团有限公司,网站内容运营方案两个节点沿二叉树向上找#xff0c;找到的第一个公共的节点 例#xff1a;D和F之间的最低公共节点#xff1a;B D → B#xff1b; F → E → B#xff1b; E和G最低公共节点#xff1a;A E → B → A#xff1b; G → C → A#xff1b; B和F最低公共节点#xff…
两个节点沿二叉树向上找找到的第一个公共的节点 例D和F之间的最低公共节点B D → B F → E → B E和G最低公共节点A E → B → A G → C → A B和F最低公共节点B B F → E → B 方法一
从两个节点开始生成两条有向无环链表
优化生成链表主要是为了寻找node1节点的所有父节点但是对于其中的节点关系没有要求所以我们可以不使用链表结构而使用HashSet结构
package binarytree;import java.util.HashMap;
import java.util.HashSet;public class LowestCommonAncester {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value data;}}public Node lowestCommonAncester(Node head, Node node01, Node node02) {if (head null) {return null;}HashMapNode, Node fatherMap new HashMap();//记录每个节点的父节点前为子节点后为父节点fatherMap.put(head, null);//设置头节点的父节点为nullHashSetNode set new HashSet();//记录了node01的所有父节点HashSet集合不保证数据的有序性set.add(node01);//先把node01放进去while (node01 ! head) {set.add(fatherMap.get(node01));//把父节点放入set集合中node01 fatherMap.get(node01);//将node01修改为它的父节点向上查询}while (node02 ! head) {if (set.contains(node02)) {//set集合中存在node02节点向上查询的第一个公共节点即为最低公共节点return node02;}node02 fatherMap.get(node02);//将node02修改为它的父节点向上查询}//在node01到头节点的set集合中都没有找到两个节点的公共节点那么它们一定有个公共节点为头节点return head;}//此方法记录fatherMap集合的数据。即每个节点的父节点public void process(Node node, HashMapNode, Node fatherMap) {fatherMap.put(node.left, node);//左孩子的父节点是他自己fatherMap.put(node.right, node);//右孩子的父节点是他自己process(node.left, fatherMap);process(node.right, fatherMap);}
}方法二
找到的最低公共节点有三种情况 node1是两节点的最低公共节点node1是node2的其中一个父节点 node2是两节点的最低公共节点node2是node1的其中一个父节点 node1和node2无关两个节点向上查询找到最低公共节点 对于情况一和情况二当一个节点左右节点一个返回值一个返回空的时候选择返回值 对于情况三当一个节点左右都不为空的时候返回它自己 public Node lowestAncestor(Node node, Node node1, Node node2) {if (node null || node node1 || node node2) {//没有节点或遇到了node1或node2直接返回当前节点return node;//二叉树最底层的返回遍历到最底层或者遇到node1和node2节点}Node left lowestCommonAncester(node.left, node1, node2);//从左侧返回的node或者nullNode right lowestCommonAncester(node.right, node1, node2);//从右侧返回的node或者nullif (left ! null right ! null) {//当前节点左右返回的值都不为空return node;}return left ! null ? left : right;//如果left返回的值为null就返回右侧right返回的值如果不是null返回left的值}
