04求二叉树两个结点的最低公共祖先节点,给出代码实现
本道是大厂高频代码实现题,主要有3个核心点1.对每个结点的孩子进行递归遍历,如果左孩子里一个需求结果都没有,就不是祖先节点2.如果两个结点都在一侧出来,也不是最低祖先结点。3.最低孩子结点只可能是一左一右,而且具体镜像性,就是可以结点1在左,也可能结点2在左,不要忘记加一个elseTreeNodegetLastCommonParent(TreeNoderoot,TreeNodet1,TreeNodet2){if(findNode(root.left,t1)){if(findNode(root.right,t2)){returnroot;}else{returngetLastCommonParent(root.left,t1,t2);}}else{if(findNode(root.left,t2)){returnroot;}else{returngetLastCommonParent(root.right,t1,t2)}}}//查找节点node是否在当前二叉树中booleanfindNode(TreeNoderoot,TreeNodenode){if(root==null||node==null){returnfalse;}if(root==node){returntrue;}booleanfound=findNode(root.left,node);if(!found){found=findNode(root.right,node);}returnfound;}
来自:二叉树-二叉树遍历