算法笔记|Day15二叉树V

• ☆☆☆☆☆leetcode 654.最大二叉树
• • 题目分析
  • 代码
• ☆☆☆☆☆leetcode 617.合并二叉树
• • 题目分析
  • 代码
• ☆☆☆☆☆leetcode 700.二叉搜索树中的搜索
• • 题目分析
  • 代码
• ☆☆☆☆☆leetcode 98.验证二叉搜索树
• • 题目分析
  • 代码

☆☆☆☆☆leetcode 654.最大二叉树

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

题目分析

递归，采用前序遍历，构造中间节点，然后递归构造左子树和右子树。用数组构造二叉树，每次分隔通过下标索引直接在原数组上操作，这样可以节约时间和空间上的开销。

代码

class Solution {     public TreeNode constructMaximumBinaryTree(int[] nums) {         return construct(nums,0,nums.length);     }      public TreeNode construct(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 maxVal=nums[maxIndex];         for(int i=left;i             if(nums[i]>maxVal){                 maxVal=nums[i];                 maxIndex=i;             }         }         TreeNode root=new TreeNode(maxVal);         root.left=construct(nums,left,maxIndex);         root.right=construct(nums,maxIndex+1,right);         return root;     } } 

提示：根据maxIndex划分左右子树。

☆☆☆☆☆leetcode 617.合并二叉树

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

题目分析

递归，采用前序、中序、后序遍历均可，前序遍历更符合理解的逻辑。

代码

class Solution {     public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {         TreeNode root=new TreeNode();         if(root1==null)             return root2;         if(root2==null)             return root1;         root.val=root1.val+root2.val;         root.left=mergeTrees(root1.left,root2.left);         root.right=mergeTrees(root1.right,root2.right);         return root;     } } 

提示：新建root，没有在root1和root2上直接做修改。

☆☆☆☆☆leetcode 700.二叉搜索树中的搜索

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

题目分析

二叉搜索树自带顺序，采用递归无需考虑前序、中序、后序遍历，另外可以使用迭代法层序遍历，根据平衡二叉树的特性判断向左还是向右迭代。

代码

1.递归 class Solution {     public TreeNode searchBST(TreeNode root, int val) {         if(root==null||root.val==val)             return root;         if(root.valval)             return searchBST(root.left,val);         return null;     } } 

2.迭代 class Solution {     public TreeNode searchBST(TreeNode root, int val) {         while(root!=null){             if(root.valval)                 root=root.left;             else                 return root;         }         return null;     } } 

☆☆☆☆☆leetcode 98.验证二叉搜索树

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

题目分析

若采用中序遍历，可以把二叉树转换为一个数组，只需判断这个数组是否为有序数组。这里采用递归，用中序遍历，并用pre指针表示上一个节点，依次判断。

代码

class Solution {     TreeNode pre;      public boolean isValidBST(TreeNode root) {         if(root==null)             return true;         if(isValidBST(root.left)==false)             return false;         if(pre!=null&&pre.val>=root.val)             return false;         pre=root;         return isValidBST(root.right);     } }