-
求二叉树两节点的最小父节点(有父节点指针)
2015-09-13 21:20:06给定一颗二叉树,以及其中的两个node(地址均非空),要求给出这两个node的一个公共父节点,使得这个父节点与两个节点的路径之和最小。描述你程序的最坏时间复杂度,并实现具体函数,函数输入输出请参考如下的函数...给定一颗二叉树,以及其中的两个node(地址均非空),要求给出这两个node的一个公共父节点,使得这个父节点与两个节点的路径之和最小。描述你程序的最坏时间复杂度,并实现具体函数,函数输入输出请参考如下的函数原型:
C++函数原型:strucy TreeNode{ TreeNode* left; //指向左子树 TreeNode* right; //指向右子树 TreeNode* father; //指向父亲节点 }; TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second){ }
思路一:我们首先找到两个节点的高度差,然后从较靠近根结点的一层开始向上找,若父节点为同一节点则该节点为解。intgetHeight(TreeNode *node) { intheight = 0; while(node) { height++; node = node->parent; } returnheight; } TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second) { intheight1 = getHeight(first), height2 = getHeight(second), diff = height1 - height2; if(diff < 0) { diff = -diff; while(diff--) { second = second->parent; } } else{ while(diff--) { first = first->parent; } } while(first != second) { first = first->parent; second = second->parent; } returnfirst; }
思路二:若允许浪费空间,那么可以用两个Stack来存储从first和second到根结点的各个节点,然后出栈时比较地址是否一致,最后一个地址一致的节点为解。两种方法最坏时间复杂度均为O(n)。 -
235-236. Lowest Common Ancestor of a Binary Search Tree [Easy & Medium] 最小父节点
2019-06-24 15:33:00235. Lowest Common Ancestor of a Binary Search Tree 235. Lowest Common Ancestor of a...如果大于最大值,则所求在左子树,如果小于最小值,则所求在右子树,否则,返回当前节点 # Definition for a bina...235. Lowest Common Ancestor of a Binary Search Tree
235. Lowest Common Ancestor of a Binary Search Tree- 如果大于最大值,则所求在左子树,如果小于最小值,则所求在右子树,否则,返回当前节点
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): #循环 def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ while root: if root.val > max(p.val, q.val): root = root.left elif root.val < min(p.val, q.val): root = root.right else: return root #递归 def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ if root.val > max(p.val, q.val): return self.lowestCommonAncestor(root.left, p, q) elif root.val < min(p.val, q.val): return self.lowestCommonAncestor(root.right, p, q) else: return root #找路径后比较 def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ l1 = self.findPath(root, p) l2 = self.findPath(root, q) res = root for i in range(min(len(l1), len(l2))): if l1[i] == l2[I]: res = l1[I] else: break return res def findPath(self, root, p): res = [] while root.val != p.val: res.append(root) if root.val > p.val: root = root.left else: root = root.right res.append(p) return res
236. Lowest Common Ancestor of a Binary Tree
236. Lowest Common Ancestor of a Binary Tree# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ mydic = {} l1 = self.findPath(root, p) l2 = self.findPath(root, q) res = root for i in range(min(len(l1), len(l2))): if l1[i] == l2[I]: res = l1[I] else: break return res def findPath(self, root, p): res = [] mydic = {} qu = [root] while qu: node = qu.pop(0) if node == p: break else: if node.left: qu.append(node.left) mydic[node.left] = node if node.right: qu.append(node.right) mydic[node.right] = node while node != root: res.append(node) node = mydic[node] res.append(root) return res[::-1]
-
二叉树中2个节点的最小公共父节点
2017-01-19 15:17:03关于如何求二叉树2个节点的最小公共父节点,分2种情况讨论 情况1:节点有parent节点 这种情况就直接找到节点1和节点2的根节点,然后求得2个链表的长度,再求得长度差。如果说2条链子的长度差为n,那么 就长的...关于如何求二叉树2个节点的最小公共父节点,分2种情况讨论
情况1:节点有parent节点
这种情况就直接找到节点1和节点2的根节点,然后求得2个链表的长度,再求得长度差。如果说2条链子的长度差为n,那么
就长的节点先移动n步,然后和短的节点一起移动,并且判断父节点是否相等。那么这边其实也解决了另一个问题,就是求2个链表
的交点。
public static Node publicNode(Node node1,Node node2){
//接下来是求2个条链的起始点
int length1 = getLength(node1);
int length2 = getLength(node2);
Node firstNode,secondNode;
int res = 0;
if(length1>=length2)
res = length1 - length2;
for(int i = 0;i<res;i++){
firstNode = firstNode.parent;
}
else{
res = length2 - length1;
for(int i = 0;i<res;i++){
secondNode = secondNode.parent;
}
// 接下来是从起始节点开始找交点
while(firstNode.parent!=null||secondNode.parent!=null){
if(node1.parent==node2.parent)
return node1.parent;
else{
firstNode = firstNode.parent;
secondNode = secondNode.parent;
}
}
}
其实会这么一个问题,就会求链表的交点和求二叉树的2个节点的最小公共父节点了。
情况2,节点没有parent节点
这个其实也简单,就是从根节点开始层次遍历这棵树,然后判断当前节点是否包含2个节点,如果包含就继续遍历当前节点的
左右节点是否包含这2个节点,如果包含就继续深入。如果左右都不包含,那么当前节点就是最小公共父节点。
public static Node getPublicNode(Node node1,Node node2){
//获得根节点,并且对根节点进行层次遍历
Node root = getRoot(node1);
Deque<Node> deque = new Deque<Node>();
deque.add(root);
while(deque.size()!=0){
Node node = deque.peekFirst();
if(node.containChilds(node1,node2)){
//当当前节点包含2个节点,而它的左右节点都不包含2个节点,那么它就是最小公共父节点
if(node.left!=null&&node.right!=null&&!node.right.containChilds&&!node.left.containChilds){
return node;
}
if(node.left!=null&&node.left.containChilds(node1,node2))
deque.add(node.left);
if(node.right!=null&&node.right.containChilds(node1,node2))
deque.add(node.right);
}
}
}
-
二叉树之最小公共父节点
2013-10-15 20:36:35import java.util.LinkedList; public class CommonFather { ... * 思路:最原始的方法,从根开始,分别寻找从根节点到每个目标节点的路径,然后比较 两条路径,找到最小的公共父节点。 *package com.Tree;
import java.util.LinkedList;
public class CommonFather {
/**
* 题目描述:给定一棵二叉树,要求找到其中任意两节点的最小公共父节点。
* 思路:最原始的方法,从根开始,分别寻找从根节点到每个目标节点的路径,然后比较 两条路径,找到最小的公共父节点。
* @param args
* @author Adai
*/
private LinkedList<TNode> path;
private static class TNode{
int data;
TNode leftchild;
TNode rightchild;
public TNode(int da){
this.data=da;
this.leftchild=null;
this.rightchild=null;
}
}
private TNode root;
public CommonFather(int[] list){
TNode curr=null;
for(int i=0;i<list.length;i++){
TNode now=new TNode(list[i]);
if(i==0){
root=now;
curr=root;
}else{
curr=root;
while(curr!=null){
if(curr.data<now.data){
if(curr.rightchild!=null){
curr=curr.rightchild;
}else{
curr.rightchild=now;
break;
}
}else{
if(curr.leftchild!=null){
curr=curr.leftchild;
}else{
curr.leftchild=now;
break;
}
}
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] list={5,4,6,3,7,2,8,1,9};
CommonFather cf=new CommonFather(list);
TNode tar=cf.FindCommonFather(cf.root, 3, 7);
System.out.println(tar.data);
}
public TNode FindCommonFather(TNode root,int t1,int t2){
if(root==null) return null;
path=new LinkedList<TNode>();
LinkedList<TNode> set=new LinkedList<TNode>();
TNode cur=root;
if(FindTNode(cur,t1)){
while(!path.isEmpty()){
TNode now=path.pop();
set.push(now);
System.out.println(now.data);
}
}else{
return null;
}
path.clear();
cur=root;
LinkedList<TNode> guest=new LinkedList<TNode>();
if(FindTNode(cur,t2)){
TNode cf=null;
while(!path.isEmpty()){
TNode now=path.pop();
System.out.println("2:"+now.data);
guest.push(now);
}
}else{
return null;
}
TNode ret=null;
while(!set.isEmpty()&&!guest.isEmpty()){
TNode se=set.pop();
TNode ge=guest.pop();
if(se.equals(ge)){
ret=se;
}else{
return ret;
}
}
return null;
}
private boolean FindTNode(TNode nowroot,int target){
path.push(nowroot);
if(nowroot==null){
path.pop();
return false;
}else if(nowroot.data==target){
return true;
}else{
if(FindTNode(nowroot.leftchild,target)){
return true;
}
if(FindTNode(nowroot.rightchild,target)){
return true;
}
path.pop();
return false;
}
}
}
-
LCA-最小公共父节点
2015-07-19 10:37:22有一个普通二叉树,AB分别为两个子节点,求AB最近(深度最浅)的公共父节点。 此题仍然是一个老题,有着多种解决方法,本文针对其中三种方法来进行分析总结。 这三种方法分别是:递归法,tarjan离线算法,RMQ在线... -
求二叉树两个节点的最小公共父节点
2012-04-21 20:40:00两个节点的最小公共父节点;二是节点在同一侧,则 r->left 或者 r->right 为 NULL,另一边返回p或者q, 那么另一边返回的就是他们的最小公共父节点。 递归有两个出口,一是没有找到p或者q,则返回NULL;... -
[LeetCode] 236 Lowest Common Ancestor of a Binary Tree 二叉树的最小共同父节点 235 二叉搜索树的最小...
2018-06-02 18:23:54Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最小共同父节点 的Follow Up。跟之前那题不同的地方是,这道题是普通是二叉树,不是二叉搜索树,所以就不能利用其特有的性质,所以我们只能在二叉树中... -
二叉树最小公共父节点
2017-08-31 10:35:01/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; ...clas -
LCA最小公共父节点的解题思路
2019-02-16 23:19:00LCA最小公共父节点解法: 1、二叉搜索树: 中序遍历是升序,前序遍历即按序插入建树的序列。 二叉搜索树建树最好用前序+中序,如果用前序建树,最坏情况会退化为线性表,超时。 最近公共祖先甲级: A1143,1151 利用... -
二叉树 最小公共父节点
2014-08-18 22:15:26#include #include #include #include #include using namespace std; struct TreeNode{ char value; TreeNode * lchild; ... TreeNode(char val, TreeNode *lch, TreeNode * rch) :value(v -
查找二叉树中x和y的最小公共父节点
2018-08-31 22:04:52查找二叉树中x和y的最小公共父节点。 代码实现:见我的github:findxandy 二、解题思路 1)写一个查找函数 findx:查找x是否在树2root中。 2)查找 root 的左孩子是否有该结点,递归。 3)查找 root ... -
leetcode 236 二叉树的最小共同父节点
2018-12-04 12:54:05给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点... -
求二叉树的最小公共父节点
2017-08-21 22:38:22现在的问题就是,给定x和y,要求他们的公共父节点,即xi(也就是 yj)。 实现 import java.util.Scanner; public class Main { public static void main (String[] args) { Scanner input= new... -
求二叉树中两节点的最小公共父节点
2012-06-01 16:59:34采用递归,深度优先遍历,找到一个节点时,返回,逐层记录遍历方向,另一个节点 同,这样深度优先遍历后,可以找到这两个节点由根节点访问的路径,然后沿着这个 路径找到分叉的地方就行了 代码: #include<... -
[LeetCode] Lowest Common Ancestor of a Binary Tree 二叉树的最小共同父节点
2017-09-28 09:48:38Lowest Common Ancestor of a Binary Tree 二叉树的最小共同父节点 Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition ... -
dom4j实现为list添加父节点_最小堆的实现
2020-12-15 15:58:58根元素是最小的元素,父节点小于它的两个子节点。树中的元素是相对有序的。如何实现堆的相对有序是关键。插入元素时,插入到数组中的最后一个元素的后面,然后与该节点的父节点比较大小。如果插入的元素小于父节点... -
[ 题解 ] [ 最小公共父节点 ] E. Family Tree
2019-10-01 00:31:22题意: ...输入N行父子关系(题中为母女)即两个名字,前者是父,后者是子; 问两只牛是什么亲属关系。 具体的输出规则(亲属关系)请见原题。 示例: Input: 7 AA ... -
Lowest Common Ancestor of a Binary Tree 二叉树中的最小公共父节点
2016-06-16 15:48:02为了找一个节点,binary search tree, 有左子树节点 右子树节点这样的规则。 可以利用二分查找来找到节点。 但这里是binary tree。如果找到我们的目标节点呢? 用遍历的方法!这是一种暴力的直接求解的办法。 -
要求给出这两个node的一个公共父节点,使得这个父节点与两个节点的路径之和最小。
2016-09-05 10:05:59给定一颗二叉树,以及其中的两个node(地址均非空),要求给出这两个node的一个公共父节点,使得这个父节点与两个节点的路径之和最小。描述你程序的最坏时间复杂度,并实现具体函数,函数输入输出请参考如下的函数... -
搜索二叉树(BST)的创建...获得最小数据的节点,查找子节点的父节点,节点删除,销毁(C语言实现)【二叉树】
2020-02-21 18:37:12查找子节点的父节点 节点删除 销毁 关于删除节点的详细说明 删除节点比较复杂所以我们进行强调: 删除节点我们分为三种情况来处理: 代码实现: BST.cpp /* 搜索二叉树的节点增加和删除。 第一种情况: 若为叶子... -
235. Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最小共同父节点
2019-09-11 23:18:36按照二叉树的性质遍历即可 #include using namespace std; struct TreeNode { int val; TreeNode lChild; TreeNode rChild;...TreeNode(int val, TreeNodel = nullptr, TreeNoder = nullptr) ...l... -
Company A面试 笔试 : 完全二叉树,三叉树的最小公共父节点问题
2015-12-13 12:46:58如果是2叉树,那又如何编程? 以下是个人代码,调试通过并有注释 /* * * Author: Bigtree * * Created on */ #include #include #include #include ...long int NodesPerL -
leetcode 235 Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最小共同父节点
2018-01-24 11:09:23如果根节点小于p和q之间的较小值,说明p和q都在右子树中,那么此时我们就进入根节点的右子节点继续递归,如果都不是,则说明当前根节点就是最小共同父节点,直接返回即可,参见代码如下: class Solution { ... -
[LeetCode] 1123. Lowest Common Ancestor of Deepest Leaves 最深叶结点的最小公共父节点
2019-09-25 02:12:15若 root 有左右子结点,说明左右子树存在,通常情况下我们会对左右子结点调用递归,那么返回的就是左右子树分别的最深叶结点的最小公共父节点,但是问题来了,就算分别知道了左右子树的最深结点的 LCA,怎么推出当前...
-
华南理工大学《电机学》期末考试试卷(含答案).pdf
-
MMM 集群部署实现 MySQL 高可用和读写分离
-
【渗透工具】python子域名扫描脚本编写
-
湖南大学马哲期末复习资料(精华版).pdf
-
暨南大学《护理综合》2010--2015历届考研习题.pdf
-
江西财经大学《大学语文》期末复习知识点总结(含答案).pdf
-
httpwatch9.3.39 pro.rar
-
用Go语言来写区块链(一)
-
day2——JavaEE and Linux
-
江西财经大学《高等数学1》期末复习题(含答案).pdf
-
面试技巧之性能测试50问.docx
-
Windows_Service_PPT_CHAP01_V1.0.ppt
-
华南理工大学《电机学》多套期末试卷(含答案).pdf
-
MaxScale 实现 MySQL 读写分离与负载均衡
-
婚姻法--期末复习资料.pdf
-
3-4 变量
-
C和C++课程
-
重学操作系统----20 | 线程的调度:线程调度都有哪些方法?
-
国外人工智能课程试卷.zip
-
MySQL 备份与恢复详解(高低版本 迁移;不同字符集 相互转换;表