题解 | #在二叉树中找到两个节点的最近公共祖先#

/*

• function TreeNode(x) {
• this.val = x;
• this.left = null;
• this.right = null;
• } */

/** *

• @param root TreeNode类
• @param o1 int整型
• @param o2 int整型
• @return int整型 */ function lowestCommonAncestor( root , o1 , o2 ) { // write code here let map=new Map() const quene=[[null,root]] // 二叉树的层序遍历，在遍历过程中记录每个节点的祖先值的字符串 while(quene.length>0){ const [parent,node]=quene.shift() let pv=node.val+'' if(parent){ pv+='.'+map.get(parent.val) } map.set(node.val,pv) if(node.left) quene.push([node,node.left]) if(node.right) quene.push([node,node.right]) } let arr1=map.get(o1).split('.') let arr2=map.get(o2).split('.') if(arr1.length>arr2.length){ [arr1,arr2]=[arr2,arr1] } // 遍历祖先少的那个结果，找到在另一个结果也有的值 return arr1.find((item)=>arr2.includes(item)) } module.exports = { lowestCommonAncestor : lowestCommonAncestor };