【随想录】Day20—第六章 二叉树 part06

本文主要是介绍【随想录】Day20—第六章 二叉树 part06，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目1: 654.最大二叉树

• 题目链接：654. 最大二叉树

---

1- 思路

每次找到数组中的最大值，来构造一个结点，之后递归构造左子树和右子树

• 由于涉及到区间分割，因此构造函数有
  • left 整型变量记录
  • right 整型变量记录

---

2- 题解

⭐ 最大二叉树 ——题解思路

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {TreeNode root = build(nums,0,nums.length);return root;}public TreeNode build(int[] nums,int left,int right){if(left>=right){return null;}if(right-left==1){return new TreeNode(nums[left]);}// 单层int maxValue = nums[left];int maxIndex= left;for(int i=left+1;i<right;i++){if(nums[i]>maxValue){maxValue = nums[i];maxIndex = i;}}// 找到最大的TreeNode root = new TreeNode(maxValue);root.left = build(nums,left,maxIndex);root.right = build(nums,maxIndex+1,right);return root;}
}

---

题目2: 合并二叉树

• 题目链接：617. 合并二叉树

---

1- 思路

递归三部曲

• 1. 递归函数参数及返回值
• 2. 终止条件
  • root1 和 root2 中间有一个 null 则返回
• 3. 单层递归逻辑
  • 将 root1.val 的值更新
  • 递归 root1.left
  • 递归 root2.right

---

2- 题解

⭐最大二叉树 ——题解思路

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;}
}

---

题目3: 700.二叉搜索树中的搜索

• 题目链接：700. 二叉搜索树中的搜索

---

1- 思路

递归三部曲实现

---

2- 题解

⭐ 二叉搜索树中的搜索 ——题解思路

class Solution {public TreeNode searchBST(TreeNode root, int val) {TreeNode res = search(root,val);return res;}public TreeNode search(TreeNode root,int val){// 终止条件if(root==null){return root;}if(root.val==val){return root;}TreeNode result = new TreeNode(0);if(root.val > val) result = search(root.left,val);if(root.val < val) result = search(root.right,val);return result;}
}

---

题目4: 98. 验证二叉搜索树

• 题目链接：98. 验证二叉搜索树

---

1- 思路

先中序遍历，将遍历结果转为数组，之后判断数组中的元素是否满足升序即可

---

2- 题解

⭐验证二叉搜索树 ——题解思路

class Solution {List<Integer> res = new ArrayList<>();public boolean isValidBST(TreeNode root) {inorderT(root);int[] nums = new int[res.size()];for(int i = 0; i < res.size();i++){nums[i] = res.get(i);}for(int i = 1; i < nums.length ;i++){if(nums[i]<=nums[i-1]){return false;}}return true;}public void inorderT(TreeNode root){if(root==null) return;inorderT(root.left);res.add(root.val);inorderT(root.right);}
}

---

这篇关于【随想录】Day20—第六章 二叉树 part06的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---