代码随想录二刷day20

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

---

一、力扣654. 最大二叉树

/*** 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 TreeNode constructMaximumBinaryTree(int[] nums) {return fun(nums, 0, nums.length-1);}public TreeNode fun(int[] nums, int strat, int end){if(strat > end)return null;int index = indexFun(nums, strat, end);TreeNode cur = new TreeNode(nums[index]);int leftStart = strat, leftEnd = index-1;int rightStart = index+1, rightEnd = end;TreeNode leftChild = fun(nums, leftStart, leftEnd);TreeNode rightChild = fun(nums, rightStart, rightEnd);cur.left = leftChild;cur.right = rightChild;return cur;}public int indexFun(int[] nums, int low, int high){int max = nums[low];int index = low;for(int i = low; i <= high; i ++){if(nums[i] > max){max = nums[i];index = i;}}return index;}
}

二、力扣617. 合并二叉树

新建的树

/*** 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 TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1 == null && root2 == null){return null;}TreeNode cur = new TreeNode();TreeNode childLeft = null;TreeNode childRight = null;if(root1 != null && root2 != null){cur.val = root1.val + root2.val;childLeft = mergeTrees(root1.left, root2.left);childRight = mergeTrees(root1.right, root2.right);}if(root1 != null && root2 == null){cur.val = root1.val;childLeft = mergeTrees(root1.left, null);childRight = mergeTrees(root1.right, null);}if(root1 == null && root2 != null){cur.val = root2.val;childLeft = mergeTrees(null, root2.left);childRight = mergeTrees(null, root2.right);}cur.left = childLeft;cur.right = childRight;return cur;}
}

在原本的树上更新

/*** 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 TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1 == null)return root2;if(root2 == null)return root1;root1.val += root2.val;root1.left = mergeTrees(root1.left, root2.left);root1.right = mergeTrees(root1.right, root2.right);return root1;}
}

迭代

/*** 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 TreeNode mergeTrees(TreeNode root1, TreeNode root2) {Deque<TreeNode> deq = new LinkedList<>();if(root1 == null)return root2;if(root2 == null)return root1;deq.offerLast(root1);deq.offerLast(root2);while(!deq.isEmpty()){TreeNode p1 = deq.pollFirst();TreeNode p2 = deq.pollFirst();p1.val = p1.val + p2.val;if(p1.left != null && p2.left != null){deq.offerLast(p1.left);deq.offerLast(p2.left);}if(p1.right != null && p2.right != null){deq.offerLast(p1.right);deq.offerLast(p2.right);}if(p1.left == null && p2.left != null){p1.left = p2.left;}if(p1.right == null && p2.right != null){p1.right = p2.right;}}return root1;}
}

三、力扣700. 二叉搜索树中的搜索

递归

/*** 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 TreeNode searchBST(TreeNode root, int val) {if(root == null)return null;if(root.val < val){return searchBST(root.right, val);}if(root.val > val){return searchBST(root.left, val);}return root;}
}

迭代

/*** 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 TreeNode searchBST(TreeNode root, int val) {Deque<TreeNode> deq = new LinkedList<>();deq.offerLast(root);while(!deq.isEmpty()){TreeNode p = deq.pollFirst();if(p == null)return null;if(p.val == val)return p;if(p.val > val){deq.offerLast(p.left);}if(p.val < val){deq.offerLast(p.right);}}return null;}
}

四、力扣98. 验证二叉搜索树

递归

/*** 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 {List<Integer> path = new ArrayList<>();public boolean isValidBST(TreeNode root) {inOrder(root);for(int i = 0; i < path.size()-1; i ++){if(path.get(i) >= path.get(i+1)){return false;}}return true;}public void inOrder(TreeNode root){if(root == null){return;}inOrder(root.left);path.add(root.val);inOrder(root.right);}
}

迭代

/*** 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 {List<Integer> path = new ArrayList<>();public boolean isValidBST(TreeNode root) {Deque<TreeNode> deq = new LinkedList<>();TreeNode p  = root;while(!deq.isEmpty() || p != null){if(p != null){deq.offerLast(p);p = p.left;}else{p = deq.pollLast();path.add(p.val);p = p.right;}}for(int i = 0; i < path.size()-1; i ++){if(path.get(i) >= path.get(i+1)){return false;}}return true;}
}