本文主要是介绍代码随想录算法训练营（JAVA）| 第六章 二叉树 part06，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今日任务
力扣 654. 最大二叉树， 617. 合并二叉树，700. 二叉搜索树中的搜索，98. 验证二叉搜索树
题目 ：654. 最大二叉树
思路
使用递归地方法遍历，每次找到当前数组中的最大值。很像 前序遍历
递归三部曲
①确定递归函数的参数和返回值
参数传入的是存放元素的数组，返回该数组构造的二叉树的头结点，返回类型是指向节点的指针。
②确定终止条件
题目中说了输入的数组大小一定是大于等于1的，所以我们不用考虑小于1的情况，那么当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了。
那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。 这表示一个数组大小是1的时候，构造了一个新的节点，并返回。
③确定单层递归的逻辑
1）先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。
2）最大值所在的下标左区间 构造左子树
这里要判断maxValueIndex > 0，因为要保证左区间至少有一个数值。
3）最大值所在的下标右区间 构造右子树
判断maxValueIndex < (nums.size() - 1)，确保右区间至少有一个数值。
题解
class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return func(nums, 0, nums.length);}public TreeNode func(int[] nums, int start, int end) {if (start == end) return null;int maxIndex = start;int maxValue = nums[start];for (int i = start + 1; i < end; i++ ) {if (nums[i] > maxValue) {maxValue = nums[i];maxIndex = i;}}TreeNode node = new TreeNode(maxValue);node.left = func(nums, start, maxIndex);node.right = func(nums, maxIndex + 1, end);return node;}
}题目 ：617. 合并二叉树
思路
有合并链表那题的味了，只不过这里是累加
二叉树使用递归，本题使用哪种遍历都是可以的！
递归三部曲
①确定递归函数的参数和返回值：
首先要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。
②确定终止条件：
因为是传入了两个树，那么就有两个树遍历的节点t1 和 t2，如果t1 == NULL 了，两个树合并就应该是 t2 了（如果t2也为NULL也无所谓，合并之后就是NULL）。
反过来如果t2 == NULL，那么两个数合并就是t1（如果t1也为NULL也无所谓，合并之后就是NULL）。
③确定单层递归的逻辑：
单层递归的逻辑就比较好写了，这里我们重复利用一下t1这个树，t1就是合并之后树的根节点（就是修改了原来树的结构）。
那么单层递归中，就要把两棵树的元素加到一起。
题解
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. 二叉搜索树中的搜索
思路
注意：是 二叉搜索树，当前节点不空，然后将数值和左右子树的值进行比较。最坏情况是走到最后
递归三步曲
①确定递归函数的参数和返回值
递归函数的参数传入的就是根节点和要搜索的数值，返回的就是以这个搜索数值所在的节点。
②确定终止条件
如果root为空，或者找到这个数值了，就返回root节点。
③确定单层递归的逻辑
看看二叉搜索树的单层递归逻辑有何不同。
因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。
如果root->val > val，搜索左子树，如果root->val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。
题解
class Solution {public TreeNode searchBST(TreeNode root, int val) {while (root != null) {if (root.val < val) {root = root.right;} else if (root.val > val) {root = root.left;} else {return root;}}return null;}
}题目 ：98. 验证二叉搜索树
思路
无论是递归还是迭代法，核心思想就是中序遍历（利用二叉搜索树的性质）
要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。
有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。
迭代法中，定义一个pre判断当前节点值是否大于前一个结点值
题解
递归
class Solution {TreeNode max;public boolean isValidBST(TreeNode root) {if (root == null) return true;boolean left = isValidBST(root.left);if (!left) return false;if (max != null && max.val >= root.val) return false;max = root;return isValidBST(root.right);}
}迭代法
class Solution {public boolean isValidBST(TreeNode root) {if (root == null)return true;Stack<TreeNode> stack = new Stack<>();TreeNode pre = null;while (root != null || !stack.isEmpty()) {while (root != null) {stack.push(root);root = root.left;}TreeNode pop = stack.pop();if (pre != null && pre.val >= pop.val) {return false;}pre = pop;root = pop.right;}return true;}
}这篇关于代码随想录算法训练营（JAVA）| 第六章 二叉树 part06的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
