本文最后更新于:2023年3月19日 晚上
Lt235. 二叉搜索树的最近公共祖先、Lt155. 最小栈
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科 中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先 )。” 例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
1 2 3 输入: root = [6 ,2 ,8 ,0 ,4 ,7 ,9 ,null ,null ,3 ,5 ], p = 2 , q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6 。
示例 2:
1 2 3 输入: root = [6 ,2 ,8 ,0 ,4 ,7 ,9 ,null ,null ,3 ,5 ], p = 2 , q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2 , 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
思路 结合二叉搜索树的特点,当当前节点值都比 p、q 要大的时候,说明公共节点在左边,返回左子树,都要小的时候说明公共节点在右边,返回右子树。当值在两个之间时,就为公共祖先。
解答 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 var lowestCommonAncestor = function (root, p, q ) { if (!root) return null ; if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q); if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q); return root; };
设计一个支持 push
,pop
,top
操作,并能在常数时间内检索到最小元素的栈。
push(x)
—— 将元素 x 推入栈中。
pop()
—— 删除栈顶的元素。
top()
—— 获取栈顶元素。
getMin()
—— 检索栈中的最小元素。
示例: 输入:
1 2 ["MinStack" ,"push" ,"push" ,"push" ,"getMin" ,"pop" ,"top" ,"getMin" ] [[],[-2 ],[0 ],[-3 ],[],[],[],[]]
输出:
1 [null ,null ,null ,null ,-3 ,null ,0 ,-2 ]
解释:
1 2 3 4 5 6 7 8 MinStack minStack = new MinStack() minStack.push(-2 ) minStack.push(0 ) minStack.push(-3 ) minStack.getMin() minStack.pop() minStack.top() minStack.getMin()
提示:
pop
、top
和 getMin
操作总是在 非空栈 上调用。
思路 使用双栈做法,栈内每一个元素都是[min,x]的形式,min 总是存储当前位置下最小的一个元素,求最小元素时,直接求栈顶的[0]的值即可
解答 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 var MinStack = function ( ) { this .stack = []; }; MinStack.prototype.push = function (x ) { let min; if (!this .stack.length) min = x; else min = Math .min(this .stack[this .stack.length - 1 ][0 ], x); this .stack.push([min, x]); }; MinStack.prototype.pop = function ( ) { return this .stack.pop(); }; MinStack.prototype.top = function ( ) { if (this .stack.length) { return this .stack[this .stack.length - 1 ][1 ]; } }; MinStack.prototype.getMin = function ( ) { if (this .stack.length) { return this .stack[this .stack.length - 1 ][0 ]; } };