力扣热题9-二叉树专题、验证二叉搜索树
按照leetcode刷一遍:leetcode hot
88. 合并两个有序数组
刚开始想复杂了,直接填最大的就行了。
a * b
[1,2,3,0,0,0], m = 3, nums2 = [2,5,6]
待填的槽*必定在a或者a右边,直接写就可以了。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int a = m-1;
int b = n-1;
for(int i=m+n-1;i>=0;i--) {
if(a>=0&&b>=0&&nums1[a]>=nums2[b]) {
nums1[i] = nums1[a];
a--;
} else {
if(b>=0) nums1[i] = nums2[b];
else if(a>=0) return;
b--;
}
}
}
}
91. 解码方法
一眼动态规划,还ok。
class Solution {
public int numDecodings(String s) {
// 1 1 1 0 6
// a: 前前位
// b: 前位
// cur: 当前位置
// cur = ( if(b cur) ok?a:0 ) + ( if(cur) ok?b:0 )
if(s.length()==0||s.charAt(0)=='0') {
return 0;
}
int a = 1;
int b = 1;
int cur;
for(int i=1;i<s.length();i++) {
cur = 0;
if(s.charAt(i)!='0') {
cur += b;
}
if(s.charAt(i-1)=='1'||
s.charAt(i-1)=='2'&&(s.charAt(i)<='6')) {
cur += a;
}
a = b;
b = cur;
}
return b;
}
}
94. 二叉树的中序遍历
递归
递归没啥难度,应该会问非递归方法。
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderTraversal0(root,result);
return result;
}
private void inorderTraversal0(TreeNode root,List<Integer> result) {
if(root==null) {
return;
}
inorderTraversal0(root.left,result);
result.add(root.val);
inorderTraversal0(root.right,result);
}
}
非递归
非递归就是把原来用递归栈的东西自己存储起来。
前中后序就是当前结点是在左右结点之前,之间,之后来区分的。中序就是先记录其左节点的值,再记录当前结点值,再记录右结点值,需要用栈记录当前结点就可以了。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if(root==null) {
return result;
}
Deque<TreeNode> deque = new LinkedList<>();
TreeNode cur = root;
while(cur!=null) {
deque.addLast(cur);
if(cur.left!=null) {
cur = cur.left;
} else {
do {
cur = deque.pollLast();
if(cur==null) return result;
result.add(cur.val);
cur = cur.right;
} while(cur==null);
}
}
return result;
}
}
98. 验证二叉搜索树
错误答案
class Solution {
public boolean isValidBST(TreeNode root) {
if(root==null) return true;
return (root.left!=null?root.left.val<root.val:true) &&
(root.right!=null?root.right.val>root.val:true) &&
isValidBST(root.left) &&
isValidBST(root.right);
}
}
忘了考虑这种情况了:
修改了下,还是有问题没考虑到:
这错综复杂,用中序遍历吧,顺序的,应该可行。
中序遍历
随意写的,可以跑:
class Solution {
public boolean isValidBST(TreeNode root) {
if(root==null) return true;
List<Integer> list = new ArrayList<>();
inorderTrace(root,list);
for(int i=1;i<list.size();i++) {
if(list.get(i)<=list.get(i-1)) {
return false;
}
}
return true;
}
private void inorderTrace(TreeNode root,List<Integer> list) {
if(root==null) return;
inorderTrace(root.left,list);
list.add(root.val);
inorderTrace(root.right,list);
}
}
简洁写法(再看看)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if(root==null) return true;
if(!isValidBST(root.left)) {
return false;
}
if(root.val<=pre) {
return false;
}
pre = root.val;
if(!isValidBST(root.right)) {
return false;
}
return true;
}
}
101. 对称二叉树
遇事不决,递归大法。
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
return isSymmetric0(root.left,root.right);
}
private boolean isSymmetric0(TreeNode a,TreeNode b) {
if(a==null&&b==null) return true;
if(a==null||b==null||a.val!=b.val) return false;
return isSymmetric0(a.left,b.right)&&isSymmetric0(a.right,b.left);
}
}
102. 二叉树的层序遍历
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
Deque<Integer> layer = new LinkedList<>();
List<List<Integer>> result = new ArrayList<>();
if(root==null) return result;
deque.addLast(root);
layer.addLast(root.val);
TreeNode cur = root;
int curLayerCount = 1;
int lastLayerCount = 0;
while(!deque.isEmpty()) {
if(lastLayerCount==0) {
lastLayerCount = curLayerCount;
curLayerCount = 0;
result.add(new ArrayList(layer));
layer.clear();
} else {
cur = deque.pollFirst();
lastLayerCount--;
if(cur.left!=null) {
deque.addLast(cur.left);
layer.addLast(cur.left.val);
curLayerCount++;
}
if(cur.right!=null) {
deque.addLast(cur.right);
layer.addLast(cur.right.val);
curLayerCount++;
}
}
}
return result;
}
}
104. 二叉树的最大深度
递归
class Solution {
public int maxDepth(TreeNode root) {
if(root==null) return 0;
return Math.max(1+maxDepth(root.left),1+maxDepth(root.right));
}
}
105. 从前序与中序遍历序列构造二叉树
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeHelper(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
private TreeNode buildTreeHelper(int[] preorder,int preLeft,int preRight,int[] inorder,int inLeft,int inRight) {
if(inLeft==inRight) {
return new TreeNode(inorder[inLeft]);
}
if(inLeft>inRight) {
return null;
}
TreeNode node = new TreeNode(preorder[preLeft]);
int rootInorderPos = inLeft;
while(inorder[rootInorderPos]!=preorder[preLeft]) {
rootInorderPos++;
}
int leftPartSize = rootInorderPos-inLeft;
int rightPartSize = inRight-inLeft+1-1-leftPartSize;
node.left = buildTreeHelper(preorder,preLeft+1,preLeft+leftPartSize,inorder,inLeft,rootInorderPos-1);
node.right = buildTreeHelper(preorder,preLeft+leftPartSize+1,preRight,inorder,rootInorderPos+1,inRight);
return node;
}
}
108. 将有序数组转换为二叉搜索树
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return sortedArrayToBSTHelper(nums,0,nums.length-1);
}
private TreeNode sortedArrayToBSTHelper(int[] nums,int start,int end) {
if(start>end) {
return null;
}
if(start==end) {
return new TreeNode(nums[start]);
}
int mid = (start+end)/2;
TreeNode node = new TreeNode(nums[mid]);
node.left = sortedArrayToBSTHelper(nums,start,mid-1);
node.right = sortedArrayToBSTHelper(nums,mid+1,end);
return node;
}
}