题目链接：点击打开链接
题目大意：略
解题思路：略
相关企业
- 字节跳动
- 亚马逊（Amazon）
- 谷歌（Google）
- 微软（Microsoft）
- 苹果（Apple）
- 领英（LinkedIn）
- PayPal
AC 代码
- Java
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/// 解决方案(1)classSolution { Queue<TreeNode>pQue=newLinkedList<>(), qQue=newLinkedList<>(); Map<TreeNode, Integer>pMap=newHashMap<>(), qMap=newHashMap<>(); publicTreeNodelowestCommonAncestor(TreeNoderoot, TreeNodep, TreeNodeq) { dfs(root, p.val, pQue, pMap, 0); dfs(root, q.val, qQue, qMap, 0); TreeNoderes=common(); returnres; } TreeNodecommon() { TreeNoderes; while (!pQue.isEmpty() &&!qQue.isEmpty()) { TreeNodepe=pQue.peek(); TreeNodeqe=qQue.peek(); if (pe.val==qe.val) { res=pQue.peek(); pQue.poll(); qQue.poll(); returnres; } if (pMap.get(pe) >qMap.get(qe)) { pQue.poll(); } elseif (pMap.get(pe) <qMap.get(qe)) { qQue.poll(); } else { pQue.poll(); qQue.poll(); } } returnnull; } booleandfs(TreeNodenode, intval, Queue<TreeNode>queue, Map<TreeNode, Integer>map, intl) { if (node==null) { returnfalse; } if (node.val==val) { queue.offer(node); map.put(node, l); returntrue; } booleanleft=dfs(node.left, val, queue, map, l+1); if (left) { queue.offer(node); map.put(node, l); returntrue; } booleanright=dfs(node.right, val, queue, map, l+1); if (right) { queue.offer(node); map.put(node, l); returntrue; } returnfalse; } } // 解决方案(2)classSolution { publicTreeNodelowestCommonAncestor(TreeNoderoot, TreeNodep, TreeNodeq) { if(root==null||root==p||root==q) returnroot; TreeNodeleft=lowestCommonAncestor(root.left, p, q); TreeNoderight=lowestCommonAncestor(root.right, p, q); if(left==null) returnright; if(right==null) returnleft; returnroot; } }
- C++
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/classSolution { public: TreeNode*lowestCommonAncestor(TreeNode*root, TreeNode*p, TreeNode*q) { if(root==nullptr||root==p||root==q) returnroot; TreeNode*left=lowestCommonAncestor(root->left, p, q); TreeNode*right=lowestCommonAncestor(root->right, p, q); if(left==nullptr) returnright; if(right==nullptr) returnleft; returnroot; } };
