LeetCode:654.最大二叉树
1.思路
题目给出思路，递归法实现即可。
①确定递归函数function(){}的参数nums, leftIndex,rightIndex及返回值root(在单层递归里体现)
②确定单层递归的逻辑
确定终止条件（往往在第②步的内部实现）：数量为空或者为1，直接输出.
求数组区间内最大值及对应索引.
创建根节点root，作为返回值
递归遍历构建左右子树root.left = function(){};root.right= function(){};
最后，返回root.
2.代码实现
1class Solution { 2 public TreeNode constructMaximumBinaryTree(int[] nums) { 3 return function(nums, 0, nums.length); // 确定递归函数的参数及其返回值 4 } 5 6 // 确定单层递归的逻辑 7 public TreeNode function(int[] nums, int leftIndex, int rightIndex) { 8 // 确定终止条件 9 if (rightIndex - leftIndex < 1) return null; 10 if (rightIndex - leftIndex == 1) return new TreeNode(nums[leftIndex]); 11 12 // 遍历选出数组区间内最大值及其索引,作为根节点值 13 int maxIndex = leftIndex; // 最大值索引假设 14 int maxValue = nums[maxIndex]; // 索引最大值 15 for (int i = leftIndex + 1; i < rightIndex; i++) { // 区间处理很关键 16 if (nums[i] > maxValue) { 17 maxValue = nums[i]; 18 maxIndex = i; 19 } 20 } 21 // 构建根节点 22 TreeNode root = new TreeNode(maxValue); 23 // 构建左右子树 24 root.left = function(nums, leftIndex, maxIndex); 25 root.right = function(nums, maxIndex + 1, rightIndex); 26 return root; 27 } 28}
3.复杂度分析
时间复杂度：数组for()循环遍历历时O(n)，递归调用为O(n).两者嵌套为O(n²).
空间复杂度：递归函数调用n次，也即栈使用n次，则复杂度为O(n).
LeetCode:617.合并二叉树
1.思路
递归法：
怎么实现同时遍历两个树？递归函数传入两个树的根节点；
什么时间终止呢？当两棵树的左右孩子均为null时；
（前序遍历）将两节点值赋给其中的一个树相应节点即可
怎么返回结果呢？内部没有构建新树，使用的对root1的赋值操作，此时返回root1即可.
2.代码实现
1class Solution { 2 public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { 3 if (root1 == null) return root2; // 如果root1为空，返回root2 4 if (root2 == null) return root1; // 如果root2为空，返回root1 5 6 root1.val += root2.val; // 合并两个节点的值 7 root1.left = mergeTrees(root1.left, root2.left); // 递归合并左子树 8 root1.right = mergeTrees(root1.right, root2.right); // 递归合并右子树 9 return root1; // 返回合并后的根节点 10 } 11}
3.复杂度分析
时间复杂度：同时遍历两棵树是否和遍历一棵树相同？递归的时间复杂度取决于递归函数调用次数，什么时间结束递归？当节点数较小的那颗树合并完递归调用结束。因此最大时间开销取决于两树中节点较小的一棵，O(min(m,n)).
空间复杂度：调用n次函数，则栈空间开销为O(min(m,n)).
LeetCode:700.二叉搜索树中的搜索
1.思路
递归法
给定函数及参数即为递归函数及参数；
（前序遍历）定义指向null的新节点，存储root.val == val 的节点；
2.代码实现
1class Solution { 2 public TreeNode searchBST(TreeNode root, int val) { 3 // 前序递归遍历二叉树 4 5 if (root.val == val || root == null) return root; // 如果根节点为空或者根节点的值等于目标值，直接返回根节点 6 TreeNode res = null; // 初始化结果节点为null 7 if (root.val > val) { 8 res = searchBST(root.left, val); // 递归搜索左子树 9 } else { 10 root.right = searchBST(root.right, val); // 递归搜索右子树 11 } 12 return res; // 返回结果节点 13 } 14}
迭代法：
1class Solution { 2 public TreeNode searchBST(TreeNode root, int val) { 3 while (root != null) { 4 if (root.val == val) return root; 5 else if (root.val > val) root = root.left; 6 else root = root.right; 7 } 8 return null; 9 } 10}
3.复杂度分析
时间复杂度：二叉树遍历最坏情况是单链表的二叉树，此时递归函数调用了n次，则为O(n).均值的普通二叉树为O(log(n)).
空间复杂度：介于O(logn)与O(n)之间.
LeetCode:98.验证二叉搜索树
1.思路
二叉树搜索树的特性：中序遍历的树是有序的。
树值为null时，二叉搜索树、完全二叉树、满二叉树、平衡二叉树
（中序遍历）
2.代码实现
1class Solution { 2 TreeNode max; // 用于保存当前节点的最大值 3 public boolean isValidBST(TreeNode root) { 4 if (root == null) { 5 return true; // 空树为有效的二叉搜索树 6 } 7 // 左 8 boolean left = isValidBST(root.left); // 判断左子树是否为有效的二叉搜索树 9 if (!left) { 10 return false; // 如果左子树不是有效的二叉搜索树，直接返回false 11 } 12 // 中 13 if (max != null && root.val <= max.val) { 14 return false; // 如果当前节点的值小于等于最大值，说明不满足二叉搜索树的定义，返回false 15 } 16 max = root; // 更新最大值为当前节点 17 // 右 18 boolean right = isValidBST(root.right); // 判断右子树是否为有效的二叉搜索树 19 return right; // 返回右子树的结果 等价于 if (!right) { 20 return false; 21 } 22 return true; 23 } 24}
3.复杂度分析
时间复杂度：递归调用n次，则为O(n).
空间复杂度：递归调用n次，而最坏情况二叉树为链表，则栈空间开销为O(n).正常为O(logn).
