外贸网站品牌官网建设,网络布线,wordpress调用编辑器,腾讯3大外包公司二叉树 part06 654.最大二叉树解题思路 617.合并二叉树解题思路 700.二叉搜索树中的搜索解题思路 98.验证二叉搜索树解题思路误区 654.最大二叉树 又是构造二叉树#xff0c;昨天大家刚刚做完 中序后序确定二叉树#xff0c;今天做这个 应该会容易一些#xff0c; 先看视频昨天大家刚刚做完 中序后序确定二叉树今天做这个 应该会容易一些 先看视频好好体会一下 为什么构造二叉树都是 前序遍历 题目链接/文章讲解654.最大二叉树 视频讲解654.最大二叉树 解题思路
和昨天最后2道题思路类似比那2道题处理起来还更简单一些 解题步骤
递归终止条件判断只有1个元素/没有元素找最大值将其加入树根据最大值所在下标划分左右子树
注意点
用下标来确定左右子树的遍历范围不用开辟新空间所有区间范围统一一个原则这里是左闭右开
class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return constructMaximumBinaryTree1(nums, 0, nums.length);}public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex){if(rightIndex - leftIndex 1) return null; // 没有元素了if(rightIndex - leftIndex 1) return new TreeNode(nums[leftIndex]); //只有1个元素表明到了叶子节点// 找最大值及最大值所在位置int maxIndex leftIndex; // 最大值所在位置int maxVal nums[maxIndex]; // 最大者所在下标for(int i leftIndex 1; i rightIndex; i){if(nums[i] maxVal){maxVal nums[i];maxIndex i;}}TreeNode root new TreeNode(maxVal);// 根据maxIndex划分左右子树root.left constructMaximumBinaryTree1(nums, leftIndex, maxIndex);root.right constructMaximumBinaryTree1(nums, maxIndex 1, rightIndex);return root;}
}617.合并二叉树 这次是一起操作两个二叉树了 估计大家也没一起操作过两个二叉树也不知道该如何一起操作可以看视频先理解一下。 优先掌握递归。 题目链接/文章讲解617.合并二叉树 视频讲解617.合并二叉树 ## 解题思路 解题思路
考查同时对两个二叉树同时操作 理论上前中后序遍历都可以层序迭代也可以。但是leecode要求必须从根节点开始合并所以只能用前序或者层序。 思路
终止条件两棵树遍历的当前节点至少有一个为null单层递归逻辑把两棵树的值加到一起
// 递归 前序
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1 null) return root2;if(root2 null) return root1;TreeNode root new TreeNode(0);// 中root.val root1.val root2.val;// 左root.left mergeTrees(root1.left, root2.left);// 右root.right mergeTrees(root1.right, root2.right);return root;}
}// 使用队列迭代
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1 null) return root2;if (root2 null) return root1;QueueTreeNode queue new LinkedList();queue.offer(root1);queue.offer(root2);while (!queue.isEmpty()) {TreeNode node1 queue.poll();TreeNode node2 queue.poll();// 此时两个节点一定不为空val相加node1.val node1.val node2.val;// 如果两棵树左节点都不为空加入队列if (node1.left ! null node2.left ! null) {queue.offer(node1.left);queue.offer(node2.left);}// 如果两棵树右节点都不为空加入队列if (node1.right ! null node2.right ! null) {queue.offer(node1.right);queue.offer(node2.right);}// 若node1的左节点为空直接赋值if (node1.left null node2.left ! null) {node1.left node2.left;}// 若node1的右节点为空直接赋值if (node1.right null node2.right ! null) {node1.right node2.right;}}return root1;}
}700.二叉搜索树中的搜索 递归和迭代 都可以掌握以下因为本题比较简单 了解一下 二叉搜索树的特性 题目链接/文章讲解: 700.二叉搜索树中的搜索 视频讲解700.二叉搜索树中的搜索 解题思路
二叉搜索树是一个有序树它的递归遍历和迭代遍历和普通二叉树都不一样。
终止条件root为空或者找到这个数值单层递归逻辑因为二叉搜索树的节点是有序的所以可以有方向的去搜索。 如果root.val val搜索左子树如果root.val val就搜索右子树最后如果都没有搜索到就返回NULL。
// 递归
class Solution {public TreeNode searchBST(TreeNode root, int val) {if(root null || root.val val) return root;TreeNode result null;if(root.val val) result searchBST(root.left, val);if(root.val val) result searchBST(root.right, val);return result;}
}// 层序迭代
class Solution {public TreeNode searchBST(TreeNode root, int val) {while(root ! null){if(root.val val) root root.left;else if(root.val val) root root.right; else return root; }return null;}
}98.验证二叉搜索树 但本题是有陷阱的可以自己先做一做然后在看题解看看自己是不是掉陷阱里了。这样理解的更深刻。 题目链接/文章讲解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 解题思路
遇到 搜索树一定想着中序遍历这样才能利用上特性.如果中序遍历下元素是单调递增的那它就是一颗二叉搜索树。遍历二叉搜索树时如何用两个指针比较元素大小。
误区
不能单纯的比较左节点小于中间节点右节点大于中间节点就完事了。我们要比较的是 左子树所有节点小于中间节点右子树所有节点大于中间节点。
if (root-val root-left-val root-val root-right-val) {return true;
} else {return false;
}样例中最小节点 可能是int的最小值如果这样使用最小的int来比较也是不行的。此时可以初始化比较元素为longlong的最小值。但是这样解决不是最优的可以用指针来进行比较
// 递归 中序遍历 定义TreeNode prev null;
class Solution {TreeNode prev null;public boolean isValidBST(TreeNode root) {if(root null) return true;if(!isValidBST(root.left)) return false; // 左// 中if(prev ! null root.val prev.val) return false;prev root;return isValidBST(root.right); // 右}
}// 递归 中序遍历 定义long prev
class Solution {private long prev Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root null) return true;if(!isValidBST(root.left)) return false; // 左// 中if(root.val prev) return false;prev root.val;return isValidBST(root.right); // 右 }
}
