LeetCode in python简单题–二叉树篇-叭楼楼市分享网

楼市新闻、行业动态
叭楼，新房带看，二手房代办过户，望京二手房精选房源，您置业的小管家。

二叉树也是算法面试中的高频考点，本篇梳理leetcode中二叉树的简单题，随后下一篇梳理二叉树的中等题。二叉树简单题整理了13个，我只做了题号前500的题目。

提纲

100. 相同的树

101. 对称二叉树

104. 二叉树的最大深度

107. 二叉树的层次遍历 II

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

110. 平衡二叉树

111. 二叉树的最小深度

112. 路径总和

226. 翻转二叉树

235. 二叉搜索树的最近公共祖先

257. 二叉树的所有路径

404. 左叶子之和

437. 路径总和 III

100. 相同的树

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 :

输入:      1         1
          / \       / \
         2   3     2   3
        [1,2,3],   [1,2,3]
输出: true

思路

二叉树的问题，通常通过递归的思想来解决。如果两棵树都是空树，返回True，如果两棵树都不是空，那么分别判断两棵树的根节点的数值，左结点和右结点是否相同。

代码

class Solution(object):
    def isSameTree(self, p, q):
        if p is None and q is None:
            return True
        if p is not None and q is not None:
            return p.val==q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        return False

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

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

思路

这个题思路和100题有点类似，依然是递归的思想，首先判断头结点是否为空。然后将根节点的左右两个节点假设成两个独立的树，如果左右两个树都为空，返回True。然后看左子树的左结点和右子树的右结点、左子树的右结点和右子树的左结点是否相同，都相同返回True.

代码

class Solution(object):
    def isSymmetric(self, root):
        if root is None:
            return True
        return self.isSymmetricTree(root.left,root.right)
    def isSymmetricTree(self,left,right):
        if left is None and right is None:
            return True
        if left is None or right is None or left.val != right.val:
            return False
        return self.isSymmetricTree(left.left,right.right) and self.isSymmetricTree(left.right,right.left)

104. 二叉树的最大深度

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

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

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

返回它的最大深度 3 。

思路

递归的方法，比较左边路径和右边路径哪边最长，选择最长的一边路径，加上root结点本身的长度。

代码

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

107. 二叉树的层次遍历 II

给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

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

返回其自底向上的层次遍历为：

[
  [15,7],
  [9,20],
  [3]
]

思路

一层层地输出result：[3],[9,20],[15,7]，然后翻转result [::-1]，返回[15,7],[9,20],[3]。如果不一层层输出，直接输出[3,9,20,15,7]，然后翻转变成了[7,15,20,9,3]。

代码

class Solution(object):
    def levelOrderBottom(self, root):
        if root is None:
            return []
        result,current = [],[root]
        while current:
            next_level,vals = [], []
            for node in current:
                vals.append(node.val)
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
            current = next_level
            result.append(vals)
        return result[::-1]

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

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

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

示例:

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

思路

这也是个高频题，用递归的方法找到root结点，以及左子树和右子树。

代码

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

110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 :

给定二叉树 [3,9,20,null,null,15,7]

返回 true 。

思路

利用104题中判断二叉树最大深度的函数，左子树和右子树的深度差小于等于1即为平衡二叉树。

代码

class Solution(object):
    def isBalanced(self, root):
        if root == None:
            return True
        elif abs(self.height(root.left)-self.height(root.right))>1:
            return False
        else:
            return self.isBalanced(root.left) and self.isBalanced(root.right)
    def height(self,root):
        if root == None:
            return 0
        else:
            return max(self.height(root.left),self.height(root.right))+ 1

111. 二叉树的最小深度

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

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

示例:

给定二叉树 [3,9,20,null,null,15,7],

返回它的最小深度 2.

思路

如果根节点不存在，返回0；然后找根节点的左右子节点，找到深度最小的值，然后加1。

有一个特殊情况，如果根节点只有一个结点，那么深度最小的值不是1，具体见下例。因为是到最近的叶子节点的深度。

例：           3
                \
                 4
               /   \
              5     6      这种情况下，最小深度不是1，而是3。

代码

class Solution(object):
    def minDepth(self, root):
        if root is None:
            return 0
        if root.left and root.right:
            return min(self.minDepth(root.left),self.minDepth(root.right))+1
        else:
            return max(self.minDepth(root.left),self.minDepth(root.right))+1

112. 路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

示例:
给定如下二叉树，以及目标和 sum = 22，

5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

思路

从上到下加起来，最后一个节点的值就等于sum-前面的和，且这个节点是叶子节点。

代码

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

226. 翻转二叉树

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

思路

交换左右节点

代码

class Solution(object):
    def invertTree(self, root):
        if root is not None:
            root.left,root.right = self.invertTree(root.right),self.invertTree(root.left)
        return root

235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1: 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8。输出: 6

解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2: 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4。输出: 2

解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

思路

二叉搜索树（Binary Search Tree，BST），它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

从上到下，如果这两个值都大于该节点，那么就往该节点的右节点继续查找；若都小于该节点，那么就往该节点的左节点继续查找，如果一个值等于该节点，那么该节点即为最近公共祖先。

代码

# 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 lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        pointer = root
        while pointer:
            if q.val < pointer.val and p.val < pointer.val:
                pointer = pointer.left
            elif q.val > pointer.val and p.val > pointer.val:
                pointer = pointer.right
            else:
                return pointer

257. 二叉树的所有路径

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

说明: 叶子节点是指没有子节点的节点。

示例:

输入:
   1
 /   \
2     3
 \
  5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

代码

class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        result = list()
        if root == None:
            return result
        if root.left == None and root.right == None:
            result.append(str(root.val))
            return result
        left = self.binaryTreePaths(root.left)
        for i in range(len(left)):
            result.append(str(root.val) + '->' + left[i])
        right = self.binaryTreePaths(root.right)
        for i in range(len(right)):
            result.append(str(root.val) + '->' + right[i])
        return result

404. 左叶子之和
计算给定二叉树的所有左叶子之和。

示例：

    3
   / \
  9  20
    /  \
   15   7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

代码

class Solution(object):
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        result = 0
        if not root:
            return 0      
        if root.left and not root.left.left and not root.left.right:
            result += root.left.val
        return result+self.sumOfLeftLeaves(root.left)+self.sumOfLeftLeaves(root.right)

437. 路径总和 III

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例：

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1
返回 3。和等于 8 的路径有:
1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

思路

借助一个函数：查找从该点出发得到目标值的路径的个数。

代码

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        if not root:
            return 0
        return self.pathSumFrom(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)
    def pathSumFrom(self, node, sum):
        if not node:
            return 0
        return (1 if node.val == sum else 0) + self.pathSumFrom(node.left, sum - node.val) + self.pathSumFrom(node.right, sum - node.val)

声明：本站内容来源于网络或叭楼会员发布，叭楼只作为信息发布平台，版权归原作者所有，本站不承担任何图片、内容、观点等内容版权问题，如对内容有歧义，可第一时间联系本站管理员发送邮件8309272@qq.com或者扫码微信沟通，经核实后我们会第一时间删除。
北京二手房、楼市分析
二叉树也是算法面试中的高频考点，本篇梳理leetcode中二叉树的简单题，随后下一篇梳理二叉树的中等题。二叉树简单题整理了13个，我只做了题号前500的题目。提纲100. 相同的树 101. 对称二叉树 104. 二叉树的最大深度 107. 二叉树的层次遍历 II 108. 将有序…