Leetcode之二叉树（前200道）

持续更新...

github链接：https://github.com/x2mercy/Leetcode_Solution

为什么括号200道呢！因为准备按照200道这样的周期刷，每200道刷两遍，第一遍按难度刷，第二遍按类别刷！

先整理binarytree这一类别也是因为在刷题的过程中，由于没有系统的算法基础，这类题目算是遇到的比较大的障碍。

下面按照题目难度来说：

——————————————————————————————————————————————————————————————————————————————————————

EASY：

1. Same Tree：

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

这是我做的第一道二叉树的题目。

一开始的思路是二叉树的遍历，找到的资料：http://blog.csdn.net/bone_ace/article/details/46718683 主要说了树的构造和几种遍历方式

所以第一种方法是用层次遍历做的，代码如下：

# this solution is Time Limit Exceeded
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        result1=[]
        result1.append(p.val)
        while p:
            if p.left!=None:
                result1.append(p.left)
            if p.right!=None:
                result1.append(p.right)
        result2=[]
        result2.append(q.val)
        while q:
            if q.left!=None:
                result1.append(q.left)
            if q.right!=None:
                result1.append(q.right)
        result=cmp(result1,result2)
        if result==0:
            return True
        else:
            return False

满心欢喜的以为可以过，但是却报了time limit exceed的错误，于是开始找第二种方法！

上代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p==None and q==None:
            return True
        if p==None or q==None:
            return False
        if p.val==q.val:
            return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        return False

这种做法写完之后呢。。emmmm觉得自己上一种方法简直是智障儿童

这种方法很简单呐，重点是用了递归。递归真是一种逻辑简洁的好东西，利用递归比较子树的各个节点是否相同。

2. Symmetric Tree:

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

先上代码：

# recursive answer
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root==None:
            return True
        return self.isMirror(root.left,root.right)
    def isMirror(self,p,q):
        if p==None and q==None:
            return True
        if p==None or q==None:
            return False
        return p.val==q.val and self.isMirror(p.left,q.right) and self.isMirror(p.right,q.left)

这道题的重点在于调用了另一个函数，因为需要比较是否对称的本质是比较左子树的左节点和右子树的右节点、左子树的右节点和右子树的左节点是否相等，所以需要调用IsMirror函数，可以接收两个arg，isMirror返回的boolean值主要由节点值是否相等以及下个节点是否对称来决定，所以这里用了递归。

注意：用了递归，就一定要有递归停止的条件，不能无限循环下去

3. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

这道题算法很经典，mark一下，可以用在很多二叉树的题目中。

上代码：

#iterator
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root==None:
            return 0
        DL=self.maxDepth(root.left)
        DR=self.maxDepth(root.right)
        
        return max(DL,DR)+1

后面还有一道求最短路径的题目，和这个做法类似

主要也是用了递归，最后返回的时候注意要+1，因为返回的是节点数

4. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root==None:
            return []
        p=collections.deque()
        p.append((root,0))
        result=[]
        while p:
            node,index=p.popleft()
            if index>len(result)-1:
                result.append([node.val])
            else:
                result[index].append(node.val)
            if node.left:
                p.append((node.left,index+1))
            if node.right:
                p.append((node.right,index+1))
        result.reverse()
        return result

这里本来想用queue，但是发现了一个很神奇的东西:deque（学疏才浅。。），是python标准库里的一项，直接from collections import deque，或者像我这样collections.deque就可以用了。

它的好处在于，它可以提供类似于list的操作，比如append什么的，但是不同的是可以popleft操作，使第一位元素pop出来。（参考：http://blog.csdn.net/qins_superlover/article/details/44338415）

这一种操作对解决二叉树问题，提供了很大的帮助！比如这道题！

这道题是让我们把整个二叉树倒过来，返回从最底层到最上层的节点，给的例子是这样的：

于是我们知道了在append节点时，需要注意把它的index也append进去，这样便于后面判断是不是同一层的节点。

因为父节点下面的两个子节点的index是一样的，所以在append左边节点之后，会出现len(result）-1是大于右边节点index的，这时直接把右边节点append到result[index]中，等于是个多维array

最后再reverse一下，返回，搞定

5. Convert Sorted Array to Binary Search Tree：

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

这里第一次遇到平衡二叉树，所谓平衡二叉树要满足几个条件：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

所以又要用到递归

上代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if nums==[]:
            return None
        mid=len(nums)//2
        root=TreeNode(nums[mid])
        
        root.left=self.sortedArrayToBST(nums[:mid])
        root.right=self.sortedArrayToBST(nums[mid+1:])
        
        return root

其实这道题很简单，核心就是要找到根节点，而因为是sortedarray所以要找根节点，就直接找中间的那个元素，为了避免麻烦，用了"//"，表示取商的整数部分

然后分别对左子树和右子树用递归，这里的nums[:mid]和nums[mid+1:]，表示nums从下标为0到mid（不包括mid），nums从下标mid+1到最后

6. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root==None:
            return True
        DL=self.depth(root.left)
        DR=self.depth(root.right)
        
        if DL-DR<-1 or DL-DR>1:
            return False
        
        return self.isBalanced(root.left) and self.isBalanced(root.right)
    def depth(self,node):
        if node==None:
            return 0
        DL=self.depth(node.left)
        DR=self.depth(node.right)
        return max(DL,DR)+1

这里要注意的是判断是否为平衡二叉树，需要考虑一个节点左右子树是否都为平衡二叉树，所以在返回时需要用and来实现

调用了depth函数（前面说了，这个函数很经典很常用）

然后就是在比较高度时，要注意-1的情况

7. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root==None:
            return 0
        DL=self.minDepth(root.left)
        DR=self.minDepth(root.right)
        d=min(DL,DR)
        D=max(DL,DR)
        if DL==0 or DR==0:
            return D+1
        else:
            return d+1

看吧，这个算法真的很常用

但是要注意的是：如果某一子树路径为0，则取左右子树中最大的那个，如果都不为0，则取左右子树中最小的那个

8. Path Sum:

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if root==None:
            return False
        if root.right==None and root.left==None and root.val==sum:
            return True
        sum=sum-root.val
    
        return self.hasPathSum(root.left,sum) or self.hasPathSum(root.right,sum)

这道题最开始想复杂了，一直在想用deque()，然后一个一个节点加，但其实不用，cheat了一下，看了dicuss，发现了机智的做法！
只需要依次比较每个节点，比较完之后，sum减去这个节点，然后比较下一个（左或者右），直到sum=某个节点，则返回true
否则返回false
重点在于每次都需要sum减去这个节点值！这样如果剩下的节点值等于这个数，并且！它没有左右子树，则返回true

————————————————————————————————————————————————————————————————————————————————————

Leetcode之二叉树（前200道）

推荐阅读