leetcode 树标签的题集中在94-117之间，解法往往有递归和循环两种，前中后序遍历、树的生成、平衡二叉树要非常熟悉。

94. Binary Tree Inorder Traversal 二叉树的中序遍历(Medium)

Given a binary tree, return the inorder traversal of its nodes' values.
给定一个二叉树，返回中序遍历节点的值。

思路：中序遍历根左右，经典思想递归或者循环，其中循环的方法需要注意一下。

循环写法：

    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        res = []
        stack = []
        node = root
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            res.append(node.val)
            node = node.right
        return res

递归写法：

    def inorderTraversal1(self, root):
        res = []
        self.helper(root, res)
        return res
    def helper(self, root, res):
        if root:
            self.helper(root.left, res)
            res.append(root.val)
            self.helper(root.right, res)

96. Unique Binary Search Trees(Medium)

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
给一个整数n，返回有多少种不同的二叉排序树数量。

思路：其实该题更多的属于DP，每次固定一个根节点，左边所有的子节点小于根节点，而右边所有的节点大于根节点，可以列出F(i,n) = G(i-1) * G(n-i)。其中discuss区有个答案写的真心好，链接:Java solution DP Solution in 6 lines with explanation.

    def numTrees(self, n):
        dp = [1] * (n+1)
        for i in range(2, n+1):
            dp[i] = 0
            for j in range(1, i+1):
                dp[i] += dp[j-1] * dp[i-j]
        return dp[n]

95. Unique Binary Search Trees II(Medium)

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
给一个整数n，返回所有不同结构二叉排序树

思路：上一题的加强版，不仅给出个数还需要返回出来，思路基本一样固定一个根节点，递归出 G(i-1) *和G(n-i)

    def helper(self, first, last):
        if first > last:
            return [None] 
        if first == last:
            return [TreeNode(first)]
        res = []
        for i in range(first, last+1):
            for left in self.helper(first, i-1):
                for right in self.helper(i+1, last):
                    tree = TreeNode(i)
                    tree.left = left
                    tree.right = right
                    res.append(tree)
        return res
    
    def generateTrees(self, n):
        if n == 0:
            return []
        return self.helper(1, n)

98. Validate Binary Search Tree(Medium)

Given a binary tree, determine if it is a valid binary search tree (BST).
给定一棵树，判断其是否为合法的二叉排序树

思路：ps（二叉排序树的题常常可以想到中序遍历）两种方法，1、简单，递归中序遍历求得返回数组，循环判断是否为升序。2、非递归中序遍历 3、很巧妙，每次判断是否左子树小于父节点，右子树大于父节点，每个节点都将有一个最大值和最小值的区间，还要保存上一层遍历下来的最小值和最大值的节点，防止父节点的父节点有大于或小于孙该节点的情况。

#方法一
    def inordertraversal(self, root):
        if root is None:
            return 
        self.inordertraversal(root.left)
        self.res.append(root.val)
        self.inordertraversal(root.right)
        
    def isValidBST(self, root):
        if root is None:
            return True
        self.res = []
        self.inordertraversal(root)
        for i in range(1, len(self.res)):
            if self.res[i] <= self.res[i-1]:
                return False
        return True

    #方法二
    def isValidBST(self, root):
        stack = []
        inorder = float("-inf")
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            if root.val <= inorder:
                return False
            inorder = root.val
            root = root.right
        return True

    #方法三
    def isValidBST(self, root): 
        if root is None:
            return True
        return self.helper(root, None, None)
        
    def helper(self, root, minNode, maxNode):
        if root is None:
            return True
        if (minNode and root.val <= minNode.val) or (maxNode and root.val >= maxNode.val):
            return False
        return self.helper(root.left, minNode, root) and self.helper(root.right, root, maxNode)

99. Recover Binary Search Tree(hard)

Two elements of a binary search tree (BST) are swapped by mistake.Recover the tree without changing its structure.
2两个二叉排序树的节点被错误的交换了，请恢复这颗二叉排序树但不改变其结构

思路：依然是利用中序遍历BST的结构为升序排序，保存好前一次遍历的节点(prenode)
若第一次prenode>=root，则第一个错误节点firstnode为本次遍历节点
若第二次prenode>=root，则第二个错误节点senode为本次节点

    def Inordertravesal(self, root):
        if root is None:
            return None
        self.Inordertravesal(root.left)
        if self.firstnode is None and self.prenode and self.prenode.val >= root.val:
            self.firstnode = self.prenode
        if self.firstnode and self.prenode and self.prenode.val >= root.val:
            self.senode = root
        self.prenode = root
        self.Inordertravesal(root.right)
        
    def recoverTree(self, root):
        self.firstnode = None    
        self.senode = None
        self.prenode = None
        self.Inordertravesal(root)
        if self.firstnode and self.senode:
            self.firstnode.val, self.senode.val = self.senode.val, self.firstnode.val

100. Same Tree(easy)

Given two binary trees, write a function to check if they are the same or not.
给定两颗二叉排序树，判断是否相同。

思路：递归判断每一个节点，若都为空返回True，若一个为空一个非空或者节点值不相等返回False

    def isSameTree(self, p, q):
        if p is None and q is None:
            return True
        if p is None or q is None or p.val!=q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

101. Symmetric Tree(easy)

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
给定一颗二叉树，判断其是不是本身对称的（镜像）

思路：可以把100题当轮子用，把左右交换一下就ok了。

    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        return self.isSameTree(root.left, root.right)
        
    def isSameTree(self, p, q):
        if p is None and q is None:
            return True
        if p is None or q is None or p.val != q.val:
            return False
        return self.isSameTree(p.left, q.right) and self.isSameTree(p.right, q.left)

102. Binary Tree Level Order Traversal(easy)

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
给定一棵树，返回层次遍历节点的值

思路：层次遍历基本思路，借助队列（栈）

    def levelOrder(self, root):
        if root is None:
            return []
        queue, res = [root],[]
        while queue:
            tmp_res, queue0 = [],[]
            for i in queue:
                tmp_res.append(i.val)
                if i.left:
                    queue0.append(i.left)
                if i.right:
                    queue0.append(i.right)
            res.append(tmp_res)
            queue = queue0
        return res

103. Binary Tree Zigzag Level Order Traversal(Medium)

之字型打印
思路：102题的变形，利用队列，再对奇数层进行反转就行。

    def zigzagLevelOrder(self, root):
        if root is None:
            return []
        queue = [root]
        res = []
        while queue:
            tmpNode = []
            queue0 = [i for i in queue]
            queue = []
            for tree in queue0:
                tmpNode.append(tree.val)
                if tree.left:
                    queue.append(tree.left)
                if tree.right:
                    queue.append(tree.right)
            res.append(tmpNode)
        for i in range(0, len(res)):
            if i % 2:
                res[i].reverse()
        return res

104. Maximum Depth of Binary Tree(Easy)

二叉树的深度
思路：递归没深入一层取最大+1，非常地简洁，很多题可以当轮子用。

    def maxDepth(self, root):
        if root is None:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

105. Construct Binary Tree from Preorder and Inorder Traversal(Medium)

根据中序遍历和前序遍历重组二叉树
思路：学过数据结构应该知道中序+前序 or中序+后续可以确定一棵二叉树，关键在于中序的根节点可以严格把左右两边的子树分割开，而前序或者后续可以确定根节点的位置，递归解决方法如下：

    def buildTree(self, preorder, inorder):
        if not preorder or not inorder:
            return None
        index = inorder.index(preorder.pop(0)) #找到根节点在中序中的位置
        root = TreeNode(inorder[index])
        root.left = self.buildTree(preorder[:index], inorder[:index])
        root.right = self.buildTree(preorder[index:], inorder[index+1:])
        return root

106. Construct Binary Tree from Inorder and Postorder Traversal(Medium)

根据中序遍历和后序遍历重组二叉树。与105同理

    def buildTree(self, inorder, postorder):
        if not postorder:
            return None
        value = postorder.pop()
        ind = inorder.index(value)
        root = TreeNode(value)
        root.left = self.buildTree(inorder[:ind],postorder[:ind])
        root.right = self.buildTree(inorder[1+ind:],postorder[ind:])
        return root

108. Convert Sorted Array to Binary Search Treel(Easy)

转换排序好的数组为平衡二叉树。
思路：非常经典的生成二叉树的方法，平衡二叉树要求子树高度差为1，所以每次找到最中间的数值，进行递归即可。

    def sortedArrayToBST(self, nums):
        if not 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

109. Convert Sorted List to Binary Search Tree(Medium)

思路：108题的升级版，关键在于对链表进行二分，用pre来保存，细节要到位。

    def sortedListToBST(self, head):
        if head is None:
            return None
        if head.next is None:
            return TreeNode(head.val)
        pre = None
        slow = fast = head
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
        pre.next = None
        root = TreeNode(slow.val)
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)
        return root

110. Balanced Binary Tree(Easy)

思路：递归实现，这道题注意一下递归返回值就好了

    def dfs(self, root):
        if root is None:
            return 0
        left = self.dfs(root.left)
        right = self.dfs(root.right)
        if left == -1 or right == -1 or abs(left - right) > 1:
            return -1
        return max(left, right) + 1
    
    def isBalanced(self, root):
        return self.dfs(root) != -1

111. Minimum Depth of Binary Tree(Easy)

思路：最小树的深度，要考虑到如果树一边有孩子一边没有，那么取max，否则取min.
递归的写法：

    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        if root.left is not None and root.right is not None:
            return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
        else:
            return max(self.minDepth(root.left), self.minDepth(root.right)) + 1

遇到最小深度的题也很适合BFS：

    def minDepth(self, root):
        if root is None:
            return 0
        stack, depth = [root], 0
        while stack:
            depth += 1
            tmp = []
            for p in stack:       
                if p.left is None and p.right is None:
                    return depth
                if p.left:
                    tmp.append(p.left)
                if p.right:
                    tmp.append(p.right)
            stack = tmp
        return depth

112. Path Sum(Easy)

思路：路径和，每递归一次减去root.val即可。

    def hasPathSum(self, root, sum):
        if root is None:
            return False
        sum -= root.val
        if root.left is None and root.right is None and sum == 0:
            return True
        return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)

113. Path Sum II(Medium)

思路：与112类似，深度优先的递归方法。

    def pathSum(self, root, sum):
        if not root:
            return []
        res = []
        self.helper(root, sum, res, [])
        return res
        
    def helper(self, root, sum, res, tmp):
        if sum == root.val and root.left is None and root.right is None:
            tmp.append(root.val)
            res.append(tmp)
        else:
            if root.left:
                self.helper(root.left, sum - root.val, res, tmp + [root.val])
            if root.right:
                self.helper(root.right, sum - root.val, res, tmp + [root.val])

114. Flatten Binary Tree to Linked List(Medium)

思路：该题就是一个树转换成前序遍历的单链表，先通过dfs遍历到最后一个节点，每次保存最后一个节点pre(设为全局变量)，再回溯当前节点右孩子指向pre。

    def flatten(self, root):
        self.pre = None
        self.dfs(root)
        
    def dfs(self, root):
        if not root:
            return None
        self.dfs(root.right)
        self.dfs(root.left)
        root.right = self.pre
        root.left = None
        self.pre = root

116. Populating Next Right Pointers in Each Node(Medium)

思路: 该题为满二叉树(prefect)，层次遍历的方法比较容易想到，递归的话分两种情况，首先是root存在左右两孩子的时候，需要root.left.next = root.right如案例2->3,4->5，其次是root.next存在那么root.right.next = root.next.left 如案例5->6。
递归解法：

    def connect(self, root):
        if not root or not root.left:
            return 
        root.left.next = root.right
        if root.next:
            root.right.next = root.next.left
        self.connect(root.left)
        self.connect(root.right)

BFS解法：

    def connect(self, root):
        if root is None:
            return
        queue = [root]
        while queue:
            tmpqueue = []
            for i,q in enumerate(queue):
                if i<len(queue)-1:
                    q.next = queue[i+1]
                else:
                    q.next = None
                if q.left:
                    tmpqueue.append(q.left)
                if q.right:
                    tmpqueue.append(q.right)
            queue = tmpqueue

117. Populating Next Right Pointers in Each Node II(Medium)

思路:该题与116区别在于树的种类没有限制,递归比较复杂用BFS循环的比较方便。

    def connect(self, root):
        if not root:
            return None
        queue = [root]
        while queue:
            tmp = []
            while queue:
                node = queue.pop(0)
                if queue:
                    node.next = queue[0]
                else:
                    node.next = None
                if node.left:
                    tmp.append(node.left)
                if node.right:
                    tmp.append(node.right)
            queue = tmp

145. Binary Tree Postorder Traversal(hard)

后续遍历题：先按根右左的顺序遍历树，然后取逆序即可。

    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stack = [root]
        res = []
        while stack:
            node = stack.pop()
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
            res.append(node.val)
        return res[::-1]