代码随想录算法训练营DAY19 | 二叉树 (6)

一、LeetCode 654 最大二叉树

题目链接：654.最大二叉树https://leetcode.cn/problems/maximum-binary-tree/

思路：坚持左开右闭原则，递归划分数组元素生成左右子树。

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return travel(nums,0,nums.length);}//坚持左闭右开public TreeNode travel(int[] nums, int left, int right){//空数组，返回空值if(right - left < 1){return null;}//数组只有一个元素，为叶子节点if(right - left == 1){return new TreeNode(nums[left]);}//找到数组中的最大元素及其下标int maxIndex = left;int maxValue = nums[left];for(int i = left+1; i < right; i++){if(nums[i] > maxValue){maxIndex = i;maxValue = nums[i];}}TreeNode node = new TreeNode(nums[maxIndex]);//划分数组生成左右子树node.left = travel(nums,left,maxIndex);node.right = travel(nums,maxIndex+1,right);return node;}
}
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/

 二、LeetCode 617 合并二叉树

题目链接：617.合并二叉树https://leetcode.cn/problems/merge-two-binary-trees/submissions/502582353/

思路：前序递归遍历，处理空节点情况~

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {//处理root1和root2节点为空的情况if(root1 == null && root2 == null){return null;}if(root1 != null && root2 == null){return root1;}if(root1 == null && root2 != null){return root2;}//建立新节点TreeNode root = new TreeNode(root1.val + root2.val);//中、左、右递归遍历root.left = mergeTrees(root1.left,root2.left);root.right = mergeTrees(root1.right,root2.right);return root;}
}
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/

三、LeetCode  700 二叉树中的搜索

题目链接：700.二叉树中的搜索https://leetcode.cn/problems/search-in-a-binary-search-tree/

思路：前序遍历，非左即右~

class Solution {public TreeNode searchBST(TreeNode root, int val) {//找到空节点，说明该路径上没有符合条件的节点if(root == null){return null;}//找到符合条件的节点if(root.val == val){return root;}//前序遍历 中、左、右TreeNode left = searchBST(root.left,val);TreeNode right = searchBST(root.right,val);//非左即右return  left == null ? right : left;}
}
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/

四、小结

        静心刷题ovo