哈尔滨模板建站多少钱,筑龙网官网首页,微网站开发技术,百度网站的建设描述#xff1a;
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为#xff1a;“对于有根树 T 的两个节点 p、q#xff0c;最近公共祖先表示为一个节点 x#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大#xff08;一个节…描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 方法一
思路情况一p或者q其中一个是root,直接返回root情况二p或者q分别在root的左右子树上递归找到root情况三p和q都在左子树或右子树上这样有可能是递归后得到的情况一或者是递归后的情况二
//给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。前提q!p
//https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
//思路情况一p或者q其中一个是root,直接返回root情况二p或者q分别在root的左右子树上递归找到root
//情况三p和q都在左子树或右子树上这样有可能是递归后得到的情况一或者是递归后的情况二
//csdn:
public class Test4 {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(proot || qroot)return root;//情况一和情况二if (rootnull)return null;TreeNode rootleftlowestCommonAncestor(root.left,p,q);TreeNode rootrightlowestCommonAncestor(root.right,p,q);//情况三if(rootleft!null rootright!null)return root;//情况三下的情况二//p和q都在左子树或右子树上else if(rootleft!null rootrightnull)return rootleft;else if(rootleftnull rootright!null)return rootright;return null;//没有找到}}
方法二
思路我们用两个栈分别存储root到p和q经过的节点路径当递归到某个节点时这个节点的左右子树都没有p或者q,说明该节点不是路径上的节点出栈两个栈存储完毕后保证两个栈的大小长度一样一块出栈当出栈元素相同时就是交点 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(rootnull)return null;StackTreeNode stack_qnew Stack();StackTreeNodestack_pnew Stack();getStack(root,stack_p,p);//寻找从根节点到p节点路径getStack(root,stack_q,q);//寻找从根节点到q节点路径int size_pstack_p.size();int size_qstack_q.size();//保证连个栈的长度一样if(size_psize_q){for (int i 0; i size_p-size_q; i) {stack_p.pop();}} else if (size_psize_q) {for (int i 0; i size_q - size_p; i) {stack_q.pop();}}//一块出一个元素当元素相同时就是交点while (stack_p!null){if(stack_p.peek()stack_q.peek())return stack_p.pop();else {stack_p.pop();stack_q.pop();}}return root;}public boolean getStack (TreeNode root,StackTreeNode stack,TreeNode key){if(rootnull)return false;stack.push(root);if(rootkey)return true;boolean figleftgetStack(root.left,stack,key);if(figleft)return true;//左边找到了节点boolean figrightgetStack(root.right,stack,key);if (figright)return true;//右边找到了节点stack.pop();//该节点的左右子树都没有寻找的节点从栈上或者路径上移除return false;}
