面试经典150题(62-64)

leetcode 150道题 计划花两个月时候刷完，今天（第三十天）完成了3道(62-64)150：

62.（226. 翻转二叉树）题目描述：

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

第一版（直接递归，把每一个节点当做一个新二叉树去对待）

class Solution {public TreeNode invertTree(TreeNode root) {swapTree(root);return root;}public void swapTree(TreeNode root) {if(root==null){return ;}TreeNode left=root.left;TreeNode right=root.right;root.left=right;root.right=left;swapTree(left);swapTree(right);}
}

63.（101. 对称二叉树）题目描述：

给你一个二叉树的根节点 root ， 检查它是否轴对称。

第一版（还是递归，先把节点分为两个，左节点和右节点，当作两个新树，去比较左二叉树和右二叉树镜像翻过来时候相等）

class Solution {public boolean isSymmetric(TreeNode root) {if(root==null){return false;}TreeNode left=root.left;TreeNode right=root.right;return compareTree(left,right);}public boolean compareTree(TreeNode left,TreeNode right){if(left==null&&right==null){return true;}if(left!=null&&right!=null&&left.val==right.val){return compareTree(left.right,right.left)&&compareTree(left.left,right.right);}return false;}
}

64.（105. 从前序与中序遍历序列构造二叉树）题目描述：

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

第一版（经典题目，学数据结构时候应该都遇到过，但是我只是当时写过，学完后经常碰到但是没勇气和耐心再去写一遍。。今天不得不写）

class Solution {Map<Integer,Integer> map=new HashMap();public TreeNode buildTree(int[] preorder, int[] inorder) {for(int i=0;i<inorder.length;i++){map.put(inorder[i],i);}return buildSubTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);}public TreeNode buildSubTree(int[] preorder, int pLeft,int pRight,int[] inorder,int iLeft,int iRight) {if(pLeft>pRight||iLeft>iRight){return null;}if(pLeft==pRight){return new TreeNode(preorder[pLeft]);}TreeNode root=new TreeNode(preorder[pLeft]);int rootIndex=map.get(preorder[pLeft]);int count=rootIndex-iLeft;root.left=buildSubTree(preorder,pLeft+1,pLeft+count,inorder,iLeft,rootIndex-1);root.right=buildSubTree(preorder,pLeft+1+count,pRight,inorder,rootIndex+1,iRight);return root;}
}

今天有点发懒了。。差点不想打开电脑。。还好还好，今天真的最后一个我是看了一下讲解，然后自己就写了一版过了，就是在处理找中序的坐标时候，我没想到先把中序的用map保存一遍。。其他的和解题的递归一模一样，很有成就感！！！

第三十天了，不知道刷题对找工作有没有帮助。。但是也不知道干啥了，这几天工作活感觉要上强度了mmp，加油希望能早日跳槽吧！！！