leetcode-深度优先遍历

1. 二叉树的最大深度

   给定一个二叉树，找出其最大深度。

   二叉树的深度为根节点到最远叶节点的最长路径上的节点数。

   案例： 给出二叉树 [3,9,20,null,null,15,7]，

     3
    / \
   9  20
     /  \
    15   7

   返回最大深度为 3 。

   Python:

   class Solution:
       def maxDepth(self, root):
           """
           :type root: TreeNode
           :rtype: int
           """
           if not root: 
               return 0
           else:
               return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

   ​

2. 将有序数组转换为二叉搜索树

   将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

   此题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

   示例:

   给定有序数组: [-10,-3,0,5,9],
   
   一种可行答案是：[0,-3,9,-10,null,5]，它可以表示成下面这个高度平衡二叉搜索树：
   
         0
        / \
      -3   9
      /   /
    -10  5

   Python:

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

   ​

3. 二叉树的所有路径

   给定一个二叉树，返回从根节点到叶节点的所有路径。

   例如，给定以下二叉树:

      1
    /   \
   2     3
    \
     5

   所有根到叶路径是:

   ["1->2->5", "1->3"]

   Python:

   class Solution:
       
       def dfs(self, root, tmp):
           if not root: return
           if not root.left and not root.right:
               self.res.append('->'.join(tmp + [str(root.val)]))
           self.dfs(root.left, tmp + [str(root.val)])
           self.dfs(root.right, tmp + [str(root.val)])
       def binaryTreePaths(self, root):
           """
           :type root: TreeNode
           :rtype: List[str]
           """
           if not root: return []
           self.res = []
           self.dfs(root, [])
           return self.res

   Python:

   class Solution(object):
       def binaryTreePaths(self, root):
           """
           :type root: TreeNode
           :rtype: List[str]
           """
   
           def dfs(root, path, res):
               if not root.left and not root.right: res.append(path + str(root.val))
               if root.left: dfs(root.left, path + str(root.val) + '->', res)
               if root.right: dfs(root.right, path + str(root.val) + '->', res)
   
           res = []
           if root: dfs(root, '', res)
           return res

   ​

4. 等差数列划分

   如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。

   例如，以下数列为等差数列:

   1, 3, 5, 7, 9
   7, 7, 7, 7
   3, -1, -5, -9

   以下数列不是等差数列。

   1, 1, 2, 5, 7

   数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。

   如果满足以下条件，则称子数组(P, Q)为等差数组：

   元素 A[P], A[p + 1], …, A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。

   函数要返回数组 A 中所有为等差数组的子数组个数。

   示例:

   A = [1, 2, 3, 4]
   
   返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。

   仔细阅读题意，等差数列需连续，并且长度必须大于3。

   且，若等差数列长度为n(n>=3)，则加入一个元素，总体个数增加 (n-3).

   Python:

   class Solution:
       def numberOfArithmeticSlices(self, A):
           """
           :type A: List[int]
           :rtype: int
           """
           n = len(A)
           _sum, _count = 0, 1
           if n < 3: return 0
           for i in range(2, n):
               if A[i] - A[i-1] == A[i-1] - A[i-2]:
                   _sum += _count
                   _count += 1
               else:
                   _count = 1
           return _sum

   ​