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;
    }