网站建设与管理方向,网站建设流程分为哪几个阶段,网站运营主体,免费做网站的app二叉树进阶题目 236. 二叉树的最近公共祖先解题思路及实现思路一思路二 JZ36 二叉搜索树与双向链表描述解题思路及实现 236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为#xff1a;“对于有根树 T 的两个… 二叉树进阶题目 236. 二叉树的最近公共祖先解题思路及实现思路一思路二 JZ36 二叉搜索树与双向链表描述解题思路及实现 236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
示例 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1 输出3 解释节点 5 和节点 1 的最近公共祖先是节点 3 。 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4 输出5 解释节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身 解题思路及实现
思路一 class Solution {
public://中序遍历的变形----Findbool InOrder(TreeNode* root,TreeNode* node){if(root nullptr)return false;if(root node)return true;return InOrder(root-left,node) || InOrder(root-right,node);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root nullptr)return nullptr;//p或q是根if(root p || root q)return root;//找p找q, 注意pq一定在树中bool pInLeftInOrder(root-left,p);bool pInRight!pInLeft;bool qInLeftInOrder(root-left,q);bool qInRight!qInLeft;//判断if((pInLeft qInRight) || (pInRight qInLeft))return root;else if(pInLeft qInLeft)return lowestCommonAncestor(root-left,p,q);elsereturn lowestCommonAncestor(root-right,p,q);}
};虽然代码没问题但是运行效率太差了。分析一下上面是什么原因导致的。
如果这颗树是一个二叉搜索树我们就不需要去子树寻找了。 又或者这是一颗三叉树。 思路二 class Solution {
public://DFS-----前序遍历//我们这里是回溯回溯也是DFS特点是往回走做一些事情//关于回溯DFS前序遍历不要深究到底是什么有什么区别其实都是递归bool GetPath(TreeNode* root,TreeNode* node,stackTreeNode* st){if(root nullptr)return false;st.push(root);if(root node)return true;if(GetPath(root-left,node,st))return true;if(GetPath(root-right,node,st))return true;st.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root nullptr)return nullptr;stackTreeNode* pst;stackTreeNode* qst;GetPath(root,p,pst);GetPath(root,q,qst);while(pst.size() ! qst.size()){if(pst.size() qst.size())pst.pop();elseqst.pop();}while(pst.top() ! qst.top()){pst.pop();qst.pop();}return pst.top();}
};JZ36 二叉搜索树与双向链表
JZ36 二叉搜索树与双向链表这是一道牛客上面的题。
描述
输入一棵二叉搜索树将该二叉搜索树转换成一个排序的双向链表。如下图所示 数据范围输入二叉树的节点数0≤n≤1000二叉树中每个节点的值 0≤val≤1000 要求空间复杂度O(1)即在原树上操作时间复杂度 O(n)
注意: 1.要求不能创建任何新的结点只能调整树中结点指针的指向。当转化完成以后树中节点的左指针需要指向前驱树中节点的右指针需要指向后继 2.返回链表中的第一个节点的指针 3.函数返回的TreeNode有左右指针其实可以看成一个双向链表的数据结构 4.你不用输出双向链表程序会根据你的返回值自动打印输出
解题思路及实现 class Solution {
public://prev必须加个引用不然等到递归返回上一层的时候//明明prevcur了但是返回到上一层prev还是nullptrvoid ConvertLink(TreeNode* cur,TreeNode* prev){ if(cur nullptr)return;ConvertLink(cur-left, prev);cur-leftprev;if(prev)prev-rightcur;prevcur;ConvertLink(cur-right, prev);}TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree nullptr)return nullptr;TreeNode* prevnullptr;ConvertLink(pRootOfTree,prev);//找链表头链接之后pRootOfTree还在while(pRootOfTree-left)pRootOfTreepRootOfTree-left;return pRootOfTree;}
};
