做餐厅网站的需求分析报告,国外做电商网站有哪些方面,大连企业网站排名优化,建大网站首页题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为#xff1a;“对于有根树 T 的两个节点 p、q#xff0c;最近公共祖先表示为一个节点 x#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大#xff08;一个节点也可以是它自己的…题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为“对于有根树 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 因为根据定义最近公共祖先节点可以为节点本身。
示例三 输入root [3,5,1,6,2,0,8,null,null,7,4], p 6, q 2
输出3
解释节点 6和节点 2的最近公共祖先是节点 5
示例四
输入root [1,2], p 1, q 2
输出1 这道题同样是一道经典的二叉树题目具有很好的启发性和很好的递归价值类似于找交点但该题的难点
第一在于这颗二叉树是乱序的不是搜索二叉树不能通过判断值的大小来剪枝确定方向而且题目给的是指针不能通过值的比较来查找节点同时不能排除一颗树中出现两个值相同的节点也无法直接通过值的比较来查找。
第二在于树形结构没有parent父节点所以我们无法在遍历的时候无法通过回溯知晓它的路径。 所以理论上只要解决或能规避以上两个问题然后找出两个节点往前第一个共同的父节点就是最近的父节点了结合题目来看有三种情况
1、两个节点一个root的左子树一个在右子树这种情况下最近的公共祖先就只能是根节点。
2、两个节点都在左或者都在根节点右或是都在左最麻烦的情况需要确定路径然后找出最近的公共祖先。
3、一个节点是另一个节点的祖先直接返回该节点。 方法一暴力搜索
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:
//判断该路径中是否有目标节点用于确定目标节点是在root的左还是右bool Istree(TreeNode* root,TreeNode* cur){if(rootnullptr)return false;return rootcur||Istree(root-left,cur)||Istree(root-right,cur);//最终只要返回true就证明目标节点在此路径下}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(rootnullptr)//根为空直接返回return nullptr;if(rootp||rootq)//有一个是根节点就直接返回return root;//这里变量的创建是之后理清思路的关键四个变量p是否在左or右q是否在左or右bool pleft,pright,qleft,qright; pleftIstree(root-left,p);//如果p在root左边就为true不在就为falsepright!pleft;//直接和上面取反如果在左那一定不在右反之一定在右qleftIstree(root-left,q);qright!qleft;if((pleftqright)||(qleftpright))//如果一个在左一个在右直接返回root{return root;}else if(pleftqleft)//如果都在左直接去root的左边找{return lowestCommonAncestor(root-left,p,q);}else//如果在右直接去root右边找{return lowestCommonAncestor(root-right,p,q);}}
};
方法二用stack 来记录和删除路径最后找出公共祖先
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public://结合stack前序遍历bool Istree(TreeNode* root,TreeNode* cur,stackTreeNode* arr){if(rootnullptr)//为空直接返回falsereturn false;arr.push(root);//先插入该节点然后去它的左右子树找如果没找到最后pop掉if(curroot)//找到目标节点返回truereturn true;if(Istree(root-left,cur,arr))//去左子树找找到返回truereturn true;if(Istree(root-right,cur,arr))//去右子树找找到返回truereturn true;arr.pop();//左右都没找到直接pop然后返回falsereturn false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(rootnullptr)return nullptr;if(rootp||rootq)return root;stackTreeNode* arr1,arr2;//创建stack栈Istree(root,p,arr1);//保留p和q的路径Istree(root,q,arr2);while(arr1.size()!arr2.size())//让长的那个往上走和短的长度一致{if(arr1.size()arr2.size()){arr1.pop();}if(arr2.size()arr1.size()){arr2.pop();}}while(arr1.top()!arr2.top())//找到第一个公共祖先{arr1.pop();arr2.pop();}return arr1.top();}
};
