LeetCode 654
題目鏈接：合并二叉樹
構(gòu)建二叉樹的遞歸都是類似的模板挂捻，昨天的從中序和后序遍歷順序構(gòu)建也是相似的靶壮，在new的左右節(jié)點利用遞歸
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
題目鏈接：驗證二叉搜索樹
看到二叉搜索樹首先要想到中序遍歷顺献，只有中序遍歷才能充分利用到二叉搜索樹的性質(zhì)
這道題第一次做的時候，是先把所有的節(jié)點按照中序遍歷順序排在了list中洲劣，再遍歷比較损合；這樣比較浪費時間非区，只需要使用兩個指針卵蛉，再彈出的時候，跟上一個彈出的節(jié)點比較就行么库，也就是說傻丝，在統(tǒng)一的迭代寫法中，彈出就是在按照順序遍歷
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();
// 不需要把所有的節(jié)點都存到數(shù)組后再遍歷比較
// 每次都是和前面一個比較诉儒，記錄前一個節(jié)點就可以
TreeNode temp = stack.pop();
if(pre!=null&&pre.val>=temp.val){
return false;
}
pre = temp;
}
}
return true;
}
