155.最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈
输入：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
- 一个栈用来维护栈内元素，另一个优先队列用来维护栈内最小值。
98.验证二叉搜索树
输入：root =[5,4,6,null,null,3,7]
输出：false
- 二叉搜索树是根节点小于左子树所有节点且大于右子树所有节点，因此不能仅仅判断根节点和左孩子和右孩子的大小关系。第一次写的时候做法是，先递归查左子树和右子树是否是二叉搜索树，若不是则可以之间返回false。如果子树满足则查当前树是否满足，方法是**判断根节点是否比左孩子的最右边一排节点都大，比右孩子最左边一排节点都小。**这里不需要判断左孩子的左孩子的最右边一排(因为左孩子已经判断过)。每个节点最多被判断一次，时间O(n)。
public boolean dfs(TreeNode root)
{
if(root.left!=null&&dfs(root.left)==false)
return false;
if(root.right!=null&&dfs(root.right)==false)
return false;
TreeNode leftchild=root.left,rightchild=root.right;
TreeNode lright,rleft;
if(leftchild!=null)
{
if(leftchild.val>=root.val)
return false;
lright=leftchild.right;
while(lright!=null)
{
if(lright.val>=root.val)
return false;
lright=lright.right;
}
}
if(rightchild!=null)
{
if(rightchild.val<=root.val)
return false;
rleft=rightchild.left;
while(rleft!=null)
{
if(rleft.val<=root.val)
return false;
rleft=rleft.left;
}
}
return true;
}
- 第二种思路是一种自顶向下的递归，用区间来判断大小关系，dfs(root,low,high)中low表示root的节点的下界，high表示上界。如果root在区间内说明这个点符合以上层的二叉搜索树定义，但是下层的还不知道，递归左子树时上界设为root.val，递归右子树下界设为root.val。这种方法比较难想也比较打破常规的地方在于，根节点值与左孩子右孩子大小关系的比较交给孩子节点来进行。区间限制的是上层的树，往下层进行更新。
public boolean dfs(TreeNode root,long low,long high)
{
if(root==null) return true;
if(root.val<=low||root.val>=high) return false;
return dfs(root.left,low,root.val)&&dfs(root.right,root.val,high);
}
543.二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
输入：[1,2,3,4,5]
输出：返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
- dfs。返回左子树路径和右子树路径的最大值。
64.最小路径和
给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。**说明：**每次只能向下或者向右移动一步。
输入：grid = [[1,2,3],[4,5,6]]
输出：12
- 动规。dp[i][j]表示从起点到grid[i][j]位置,初始化第零行第零列，dp[i][j]=Math.min(dp[i][j-1]+dp[i-1][j])+grid[i][j]。
今日总结
刷题+除夕过节
|