LeetCode 654
题目链接：合并二叉树
构建二叉树的递归都是类似的模板，昨天的从中序和后序遍历顺序构建也是相似的，在new的左右节点利用递归
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1==null&&root2==null){
return null;
}
if(root1==null&&root2!=null){
return root2;
}
if(root1!=null&&root2==null){
return root1;
}
return new TreeNode(root1.val+root2.val, mergeTrees(root1.left, root2.left), mergeTrees(root1.right, root2.right));
}
LeetCode 98
题目链接：验证二叉搜索树
看到二叉搜索树首先要想到中序遍历，只有中序遍历才能充分利用到二叉搜索树的性质
这道题第一次做的时候，是先把所有的节点按照中序遍历顺序排在了list中，再遍历比较；这样比较浪费时间，只需要使用两个指针，再弹出的时候，跟上一个弹出的节点比较就行，也就是说，在统一的迭代写法中，弹出就是在按照顺序遍历
public boolean isValidBST(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>();
TreeNode pre = null;
if(root!=null) stack.push(root);
while(!stack.isEmpty()){
TreeNode cur = stack.peek();
if(cur!=null){
stack.pop();
if(cur.right!=null){
stack.push(cur.right);
}
stack.push(cur);
stack.push(null);
if(cur.left!=null){
stack.push(cur.left);
}
}else{
stack.pop();
// 不需要把所有的节点都存到数组后再遍历比较
// 每次都是和前面一个比较，记录前一个节点就可以
TreeNode temp = stack.pop();
if(pre!=null&&pre.val>=temp.val){
return false;
}
pre = temp;
}
}
return true;
}
