654.最大二叉樹
又是構(gòu)造二叉樹疯暑，昨天大家剛剛做完 中序后序確定二叉樹，今天做這個 應(yīng)該會容易一些高帖， 先看視頻缰儿，好好體會一下 為什么構(gòu)造二叉樹都是 前序遍歷
題目鏈接/文章講解：https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html?
視頻講解：https://www.bilibili.com/video/BV1MG411G7ox?
class Solution {
? ? public TreeNode constructMaximumBinaryTree(int[] nums) {
? ? ? ? if(nums.length == 0) return null;
? ? ? ? int max = -1, index = 0;
? ? ? ? for(int i = 0; i < nums.length; i ++){
? ? ? ? ? ? if(nums[i] > max){
? ? ? ? ? ? ? ? max = nums[i];
? ? ? ? ? ? ? ? index = i;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? TreeNode root = new TreeNode(max);
? ? ? ? if(nums.length == 1) return root;
? ? ? ? int[] left = sub(nums, 0, index);
? ? ? ? int[] right = sub(nums, index + 1, nums.length);
? ? ? ? root.left = constructMaximumBinaryTree(left);
? ? ? ? root.right = constructMaximumBinaryTree(right);
? ? ? ? return root;
? ? }
? ? public int[] sub(int[] array, int start, int end){
? ? ? ? int[] res = new int[end - start];
? ? ? ? int r = 0;
? ? ? ? for(int i = start; i < end; i ++){
? ? ? ? ? ? res[r ++] = array[i];
? ? ? ? }
? ? ? ? return res;
? ? }
}
617.合并二叉樹
這次是一起操作兩個二叉樹了， 估計(jì)大家也沒一起操作過兩個二叉樹散址，也不知道該如何一起操作乖阵，可以看視頻先理解一下。 優(yōu)先掌握遞歸预麸。
題目鏈接/文章講解：https://programmercarl.com/0617.%E5%90%88%E5%B9%B6%E4%BA%8C%E5%8F%89%E6%A0%91.html?
視頻講解：https://www.bilibili.com/video/BV1m14y1Y7JK?
class Solution {
? ? public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
? ? ? ? if(root1 == null) return root2;
? ? ? ? if(root2 == null) return root1;
? ? ? ? if(root1 == null && root2 == null) return null;
? ? ? ? TreeNode cur = new TreeNode(root1.val + root2.val);
? ? ? ? TreeNode left = mergeTrees(root1.left, root2.left);
? ? ? ? TreeNode right = mergeTrees(root1.right, root2.right);
? ? ? ? cur.left = left;
? ? ? ? cur.right = right;
? ? ? ? return cur;
? ? }
}
700.二叉搜索樹中的搜索
遞歸和迭代 都可以掌握以下瞪浸，因?yàn)楸绢}比較簡單， 了解一下 二叉搜索樹的特性
視頻講解：https://www.bilibili.com/video/BV1wG411g7sF?
class Solution {
? ? public TreeNode searchBST(TreeNode root, int val) {
? ? ? ? if(root == null) return null;
? ? ? ? if(root.val == val) return root;
? ? ? ? TreeNode left = searchBST(root.left, val);
? ? ? ? TreeNode right = searchBST(root.right, val);
? ? ? ? if(left != null) return left;
? ? ? ? if(right != null) return right;
? ? ? ? return null;
? ? }
}
class Solution {
? ? // 遞歸吏祸，普通二叉樹
? ? public TreeNode searchBST(TreeNode root, int val) {
? ? ? ? if (root == null || root.val == val) {
? ? ? ? ? ? return root;
? ? ? ? }
? ? ? ? TreeNode left = searchBST(root.left, val);
? ? ? ? if (left != null) {
? ? ? ? ? ? return left;
? ? ? ? }
? ? ? ? return searchBST(root.right, val);
? ? }
}
class Solution {
? ? // 遞歸对蒲，利用二叉搜索樹特點(diǎn)，優(yōu)化
? ? public TreeNode searchBST(TreeNode root, int val) {
? ? ? ? if (root == null || root.val == val) {
? ? ? ? ? ? return root;
? ? ? ? }
? ? ? ? if (val < root.val) {
? ? ? ? ? ? return searchBST(root.left, val);
? ? ? ? } else {
? ? ? ? ? ? return searchBST(root.right, val);
? ? ? ? }
? ? }
}
class Solution {
? ? // 迭代贡翘，普通二叉樹
? ? public TreeNode searchBST(TreeNode root, int val) {
? ? ? ? if (root == null || root.val == val) {
? ? ? ? ? ? return root;
? ? ? ? }
? ? ? ? Stack<TreeNode> stack = new Stack<>();
? ? ? ? stack.push(root);
? ? ? ? while (!stack.isEmpty()) {
? ? ? ? ? ? TreeNode pop = stack.pop();
? ? ? ? ? ? if (pop.val == val) {
? ? ? ? ? ? ? ? return pop;
? ? ? ? ? ? }
? ? ? ? ? ? if (pop.right != null) {
? ? ? ? ? ? ? ? stack.push(pop.right);
? ? ? ? ? ? }
? ? ? ? ? ? if (pop.left != null) {
? ? ? ? ? ? ? ? stack.push(pop.left);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return null;
? ? }
}
class Solution {
? ? // 迭代蹈矮，利用二叉搜索樹特點(diǎn)，優(yōu)化鸣驱，可以不需要棧
? ? public TreeNode searchBST(TreeNode root, int val) {
? ? ? ? while (root != null)
? ? ? ? ? ? if (val < root.val) root = root.left;
? ? ? ? ? ? else if (val > root.val) root = root.right;
? ? ? ? ? ? else return root;
? ? ? ? return null;
? ? }
}
98.驗(yàn)證二叉搜索樹
遇到 搜索樹泛鸟，一定想著中序遍歷批幌，這樣才能利用上特性缘挽。
但本題是有陷阱的，可以自己先做一做恬汁，然后在看題解闸翅，看看自己是不是掉陷阱里了再芋。這樣理解的更深刻。
題目鏈接/文章講解：https://programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
視頻講解：https://www.bilibili.com/video/BV18P411n7Q4?
應(yīng)該確保左子樹的最大值小于根節(jié)點(diǎn)的值坚冀，且根節(jié)點(diǎn)的值小于右子樹的最小值济赎。
我的
class Solution {
? ? public boolean isValidBST(TreeNode root) {
? ? ? ? if(root == null) return true;
? ? ? ? if(root.left == null && root.right == null) return true;
? ? ? ? boolean left = isValidBST(root.left);
? ? ? ? boolean right = isValidBST(root.right);
? ? ? ? if(root.left == null) return root.val < root.right.val && right;
? ? ? ? if(root.right == null) return root.left.val < root.val && left;
? ? ? ? boolean mid = root.left.val < root.val && root.val < root.right.val;
? ? ? ? return left && mid && right;
? ? }
}
root?=
[5,4,6,null,null,3,7]
添加到測試用例
輸出
true
預(yù)期結(jié)果
false
classSolution{// 遞歸TreeNodemax;publicbooleanisValidBST(TreeNoderoot){if(root==null){returntrue;}// 左booleanleft=isValidBST(root.left);if(!left){returnfalse;}// 中if(max!=null&&root.val<=max.val){returnfalse;}max=root;// 右booleanright=isValidBST(root.right);returnright;}}classSolution{// 迭代publicbooleanisValidBST(TreeNoderoot){if(root==null){returntrue;}Stack<TreeNode>stack=newStack<>();TreeNodepre=null;while(root!=null||!stack.isEmpty()){while(root!=null){stack.push(root);root=root.left;// 左}// 中，處理TreeNodepop=stack.pop();if(pre!=null&&pop.val<=pre.val){returnfalse;}pre=pop;root=pop.right;// 右}returntrue;}}
