注销主体备案与网站备案表,个人工作室网站,网页视频下载方法手机,女性时尚网站模板654.最大二叉树
力扣题目地址(opens new window)
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下#xff1a;
二叉树的根是数组中的最大元素。左子树是通过数组中最大值左边部分构造出的最大二叉树。右子树是通过数组中最大值右边部分构造出的最大…654.最大二叉树
力扣题目地址(opens new window)
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下
二叉树的根是数组中的最大元素。左子树是通过数组中最大值左边部分构造出的最大二叉树。右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树并且输出这个树的根节点。
示例 提示
给定的数组的大小在 [1, 1000] 之间。 思路
其实这个最大二叉树的定义和二叉搜索树非常像我们能想到的是先找到里面最大的节点将其放在根节点然后去它的左子树里面寻找接着去右子树里面寻找属于前序遍历。 确定递归函数参数以及返回值
public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex)
我们根据传入的数组和数组的起始结束节点来确定边界 确定终止条件
if (rightIndex - leftIndex 1) {// 没有元素了return null;}if (rightIndex - leftIndex 1) {// 只有一个元素return new TreeNode(nums[leftIndex]);}
当没有元素的时候直接退出只有一个元素的时候直接return即可 确定单层递归的逻辑 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;
通过循环找到最大值再通过递归左右最后return root即可
我们来看完整代码、
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]);}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.合并二叉树
力扣题目链接(opens new window)
给定两个二叉树想象当你将它们中的一个覆盖到另一个上时两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠那么将他们的值相加作为节点合并后的新值否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1: 注意: 合并必须从两个树的根节点开始。
思路
这道题不难我们只需要分别对两个数对应同一位置的节点进行比较并且对节点进行处理就可以采用那种遍历方式都行 确定递归方法及其参数
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;
将两个节点的值相加然后递归左右节点即可
我们来看完整代码
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;}
}
700.二叉搜索树中的搜索
力扣题目地址(opens new window)
给定二叉搜索树BST的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在则返回 NULL。
例如 在上述示例中如果要找的值是 5但因为没有节点值为 5我们应该返回 NULL。
思路
我们找到了对应target值的节点之后进行返回操作即可中间利用二叉搜索树的性质进行查找 确定递归函数及其参数
public TreeNode searchBST(TreeNode root, int val
传入节点和target值即可 确定终止条件
if (root null || root.val val) {return root;}
当根节点为空或者我们找到了对应值的节点的时候我们直接返回就行 确定单层递归逻辑
if (val root.val) {return searchBST(root.left, val);} else {return searchBST(root.right, val);}
如果root的值比target大我们就从root的左子树去递归反之亦然 我们来看完整代码
class Solution {// 递归利用二叉搜索树特点优化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);}}
}
98.验证二叉搜索树
力扣题目链接(opens new window)
给定一个二叉树判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征
节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。 思路 二叉搜索树 左节点小于中间节点小于右节点注意是所有左节点 下面这个情况是不符合的 不能单纯的比较左节点小于中间节点右节点大于中间节点就完事了。
写出了类似这样的代码
if (root-val root-left-val root-val root-right-val) {return true;
} else {return false;
} 确定终止条件
if (root NULL) return true;
递归到空节点我们返回true因为空节点也是二叉搜索树
确定单层递归逻辑 boolean left isValidBST(root.left);if (pre ! null pre.val root.val) return false;pre root; // 记录前一个节点boolean right isValidBST(root.right);return left right;
左中右中序遍历找到最左边最小的节点值然后一层一层返回去判断当前节点值是否大于pre一旦有一个节点不满足就会返回false 然后向上返回回去。
我们可以通过图示理解 5/ \3 7/ \ \
1 4 8
isValidBST(5)
├── left isValidBST(3)
│ ├── left isValidBST(1)
│ │ ├── left isValidBST(NULL) → true
│ │ ├── pre NULL → 1
│ │ └── right isValidBST(NULL) → true
│ │ └── 返回true true true
│ ├── pre 1 → 3
│ └── right isValidBST(4)
│ ├── left isValidBST(NULL) → true
│ ├── pre 3 → 4
│ └── right isValidBST(NULL) → true
│ └── 返回true true true
│ └── 返回true true true
├── pre 4 → 5
└── right isValidBST(7)├── left isValidBST(NULL) → true├── pre 5 → 7└── right isValidBST(8)├── left isValidBST(NULL) → true├── pre 7 → 8└── right isValidBST(NULL) → true└── 返回true true true└── 返回true true true
└── 返回true true true我们来看完整代码
class Solution {private TreeNode pre null; // 用来记录前一个节点public boolean isValidBST(TreeNode root) {if (root null) return true;boolean left isValidBST(root.left);if (pre ! null pre.val root.val) return false;pre root; // 记录前一个节点boolean right isValidBST(root.right);return left right;}
}
