LeetCode(算法)- 235. 二叉搜索树的最近公共祖先

简介: LeetCode(算法)- 235. 二叉搜索树的最近公共祖先

题目链接:点击打开链接

题目大意:

解题思路:

相关企业

  • 字节跳动
  • Facebook
  • 亚马逊(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;
    }
};
目录
相关文章
|
28天前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
2月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
29 2
|
2月前
【LeetCode 45】701.二叉搜索树中的插入操作
【LeetCode 45】701.二叉搜索树中的插入操作
10 1
|
2月前
【LeetCode 44】235.二叉搜索树的最近公共祖先
【LeetCode 44】235.二叉搜索树的最近公共祖先
18 1
|
2月前
【LeetCode 48】108.将有序数组转换为二叉搜索树
【LeetCode 48】108.将有序数组转换为二叉搜索树
40 0
|
2月前
【LeetCode 47】669.修剪二叉搜索树
【LeetCode 47】669.修剪二叉搜索树
10 0
|
2月前
【LeetCode 46】450.删除二叉搜索树的节点
【LeetCode 46】450.删除二叉搜索树的节点
19 0
|
2月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
20 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
121 2