阅读量:0
算法笔记|Day15二叉树V
☆☆☆☆☆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<right;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.二叉搜索树中的搜索
题目分析
二叉搜索树自带顺序，采用递归无需考虑前序、中序、后序遍历，另外可以使用迭代法层序遍历，根据平衡二叉树的特性判断向左还是向右迭代。
代码
1.递归 class Solution { public TreeNode searchBST(TreeNode root, int val) { if(root==null||root.val==val) return root; if(root.val<val) return searchBST(root.right,val); if(root.val>val) return searchBST(root.left,val); return null; } } 2.迭代 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; } } ☆☆☆☆☆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); } } 