题目链接：点击打开链接
题目大意：略
解题思路：略
相关企业
- 字节跳动
- 亚马逊（Amazon）
- 谷歌（Google）
- 微软（Microsoft）
- 腾讯（Tenent）
- 快手
- 小米集团
- 苹果（Apple）
- 领英（LinkedIn）
AC 代码
- Java
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/// 解决方案(1)classSolution { Stack<TreeNode>pStack=newStack<>(), qStack=newStack<>(); Map<TreeNode, Integer>pMap=newHashMap<>(), qMap=newHashMap<>(); publicTreeNodelowestCommonAncestor(TreeNoderoot, TreeNodep, TreeNodeq) { dfs(root, p.val, pStack, pMap, 0); dfs(root, q.val, qStack, qMap, 0); TreeNoderes=common(); returnres; } TreeNodecommon() { TreeNoderes; while (!pStack.isEmpty() &&!qStack.isEmpty()) { TreeNodepe=pStack.peek(); TreeNodeqe=qStack.peek(); if (pe.val==qe.val) { res=pStack.peek(); pStack.pop(); qStack.pop(); returnres; } if (pMap.get(pe) >qMap.get(qe)) { pStack.pop(); } elseif (pMap.get(pe) <qMap.get(qe)) { qStack.pop(); } else { pStack.pop(); qStack.pop(); } } returnnull; } voiddfs(TreeNodenode, intval, Stack<TreeNode>stack, Map<TreeNode, Integer>map, intl) { if (node==null) { return; } if (node.val==val) { stack.push(node); map.put(node, l); } elseif (node.val>val) { stack.push(node); map.put(node, l); dfs(node.left, val, stack, map, l+1); } else { stack.push(node); map.put(node, l); dfs(node.right, val, stack, map, l+1); } } } // 解决方案(2)classSolution { publicTreeNodelowestCommonAncestor(TreeNoderoot, TreeNodep, TreeNodeq) { if(p.val>q.val) { // 保证 p.val < q.valTreeNodetmp=p; p=q; q=tmp; } while(root!=null) { if(root.val<p.val) // p,q 都在 root 的右子树中root=root.right; // 遍历至右子节点elseif(root.val>q.val) // p,q 都在 root 的左子树中root=root.left; // 遍历至左子节点elsebreak; } returnroot; } } // 解决方案(3)classSolution { publicTreeNodelowestCommonAncestor(TreeNoderoot, TreeNodep, TreeNodeq) { if(root.val<p.val&&root.val<q.val) returnlowestCommonAncestor(root.right, p, q); if(root.val>p.val&&root.val>q.val) returnlowestCommonAncestor(root.left, p, q); 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) {}* };*/// 解决方案(1)classSolution { public: TreeNode*lowestCommonAncestor(TreeNode*root, TreeNode*p, TreeNode*q) { if(p->val>q->val) swap(p, q); while(root!=nullptr) { if(root->val<p->val) // p,q 都在 root 的右子树中root=root->right; // 遍历至右子节点elseif(root->val>q->val) // p,q 都在 root 的左子树中root=root->left; // 遍历至左子节点elsebreak; } returnroot; } }; // 解决方案(2)classSolution { public: TreeNode*lowestCommonAncestor(TreeNode*root, TreeNode*p, TreeNode*q) { if(root->val<p->val&&root->val<q->val) returnlowestCommonAncestor(root->right, p, q); if(root->val>p->val&&root->val>q->val) returnlowestCommonAncestor(root->left, p, q); returnroot; } };
