LeetCode

100、Same Tree

二十一、题目

给定两个二叉树，编写一个函数来检查它们是否相同。 如果两个二叉树在结构上相同并且节点具有相同的值，则认为它们是相同的。

思想：

递归思想，将问题拆成只比较当前两棵树的这两个节点，如果当前两个节点都是空，那么就返回true，如果当前这两个节点一个为空一个部位空，那肯定也不是相同的树，如果两个节点的val相同那就递归比较这两个节点的左右子树是否同上面说的那种情况，否则那就false，值不同那可定也不是相同的树。

Example 1:

Input: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] Output: true

Example 2:

Input: 1 1 / \ 2 2 [1,2], [1,null,2] Output: false

Example 3:

Input: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2] Output: false package cn.hnu.leetcode.easy; import cn.hnu.leetcode.easy.use_Class.TreeNode; public class _100_IsSameTree { public boolean isSameTree(TreeNode p, TreeNode q) { //递归的思想 //如果比较的两棵树的两个当前节点都是空,那么这两棵树相同 if(p==null&&q==null){ return true; } //如果比较的两棵树的两个当前节点一个是空另一个不是空 if(p==null&&q!=null||p!=null&&q==null){ return false; } //如果当两棵树的当前节点都不为空,那就看它们的值是否相等,如果相等都走下面的if if(p.val==q.val){ return isSameTree(p.left, q.left)&&isSameTree(p.right, q.right); } //否则无论何种情况都是false return false; } }

101、 Symmetric Tree

二十二、题目

给定一棵二叉树，检查它是否是自身成镜像（即，是否中心对称）。

思想：

同上题，先看看根节点是否为空，如果为空那么直接返回就是一个镜像树，否则应看它的左右子树，如果左右子树都为null返回true，如果一个为空一个部位空，那么返回false；如果左子树的val等于右子树的val，

例如，这个二叉树[1,2,2,3,4,3,3]是对称的：

1 / \ 2 2 / \ / \ 3 4 4 3

但是以下[1,2,2，null，3，null，3]不是：

1 / \ 2 2 \ \ 3 3 package cn.hnu.leetcode.easy; import cn.hnu.leetcode.easy.use_Class.TreeNode; public class _101_IsSymmetric { public boolean isSymmetric(TreeNode root) { //如果根节点是空 直接返回就是镜像树 if(root==null){ return true; } //否则判断它的左右子树 return isSymmetric(root.left,root.right); } private boolean isSymmetric(TreeNode left, TreeNode right) { //如果左右子树都是空，返回true if(left==null&&right==null){ return true; } //如果左子树为空，右子树不为空，或者反过来。那么返回false if(left==null&&right!=null||(left!=null&&right==null)){ return false; } //如果左子节点的val==右子节点的val 开始递归 if(left.val==right.val){ return isSymmetric(right.left, left.right)&&isSymmetric(right.right, left.left); } return false; } }

104、Maximum Depth of Binary Tree

二十三、题目

给定二叉树，找到它的最大深度。 最大深度是从根节点到最远叶节点的最长路径上的节点数。 注意：叶子是没有子节点的节点。

思想：

同样是递归，详见代码。

Example:

给定一棵树 [3,9,20,null,null,15,7],

3 / \ 9 20 / \ 15 7

返回depth = 3.

package cn.hnu.leetcode.easy; import cn.hnu.leetcode.easy.use_Class.TreeNode; public class _104_MaxDepth { public int maxDepth(TreeNode root) { if(root==null){ return 0; } int left = maxDepth(root.left); int right = maxDepth(root.right); return Math.max(left, right)+1; } }

107、Binary Tree Level Order Traversal II

二十四、题目

给定一棵二叉树。自下而上，自左向右的顺序输出它每层的节点值。

思路：

先设置一个链表resultList用于存储最终的结果，再设置一个队列queue，用于存储树的每一个节点，就是一个将树的节点放进队列然后移除队列首个位置放入一个levelList集合中，再将levelList中的元素放入到resultList的过程。期间还在不断的向队列中放入每个节点的左右子树，直到遍历到叶子节点。

例如: 给定一棵二叉树 [3,9,20,null,null,15,7],

3 / \ 9 20 / \ 15 7

返回结果如下:

[ [15,7], [9,20], [3] ] package cn.hnu.leetcode.easy; import java.util.LinkedList; import java.util.List; import cn.hnu.leetcode.easy.use_Class.TreeNode; public class _107_LevelOrderBottom { public List<List<Integer>> levelOrderBottom(TreeNode root) { //创建一个双向链表用于存储最终的元素,它包含的元素也是一个一个list LinkedList<List<Integer>> resultList = new LinkedList<List<Integer>>(); //创建一个list,其实也可以看成一个队列,保存每一个树节点 LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); //如果root为空,直接返回初始化的空resultList即可 if(root==null){ return resultList; } //将根节点放入队列中 queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); LinkedList<Integer> levelList = new LinkedList<Integer>(); for(int i = 0;i<size;i++){ //获取队列的头,但不删除 //看它的左右子节点是否为空,不为空就添加进queue队列中 if(queue.peek().left!=null){ queue.offer(queue.peek().left); } if(queue.peek().right!=null){ queue.offer(queue.peek().right); } //然后是把当前队列的头添加进levelList levelList.add(queue.poll().val); }//end for //然后是将levelList添加进resultList的首位置 //队列不为空进入下一次的while循环 resultList.add(0,levelList); }//end while //[[15,7],[9,20],[3]] return resultList; } }

108、Convert Sorted Array to Binary Search Tree

二十五、题目

给定一个数组，其中数组中的元素按升序排列，将其转换为平衡二叉树。 平衡二叉树：每个节点的两个子树的深度相差不超过1。

思路：

递归的思想，设置一个函数传入数组，数组的起始位置low，和数组最后一个元素的索引high；每一次都将数组的中间元素作为根，然后数组的左半边设置成根的左子树，每个左边的数组又遵循将其中间的设置成根，左边的设置成左子树；右子树同左子树，如此直到low>high的时候，递归结束。

Example:

Given the sorted array: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0 / \ -3 9 / / -10 5 package cn.hnu.leetcode.easy; import cn.hnu.leetcode.easy.use_Class.TreeNode; public class _108_SortedArrayToBST { public TreeNode sortedArrayToBST(int[] nums) { return binarySortTree(nums,0,nums.length-1); } //同样采用递归的方式 private TreeNode binarySortTree(int[] nums, int low, int high) { if(low>high){ return null; } //每次都是给定数组范围中间那个元素作为树的根 int mid = (low + high)/2; TreeNode node = new TreeNode(nums[mid]); //设置左节点 node.left = binarySortTree(nums, low, mid-1); //设置右节点 node.right = binarySortTree(nums, mid+1, high); return node; } }