Blog

leetcode110平衡二叉树

leetcode110 Balanced Binary Tree

Posted by BY on March 20, 2019

前言

新的一年，好好学习。尝试用python写写代码。

正文

问题来源

本问题来自leetcode上的110题。

问题描述

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

示例 1:

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

    3
   / \
  9  20
    /  \
   15   7

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

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

分析：

递归版本 先判断本节点是否为空，为空返回True；随后比较左右树高之差是否小于等于1，若不满足则直接返回False，否则递归判断左子树和右子树。

# 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 not root:
            return True
        if abs(self.depth(root.left)-self.depth(root.right)) <= 1:
            return self.isBalanced(root.left) and self.isBalanced(root.right)
        return False
    def depth(self, root):
        if not root:
            return 0
        return max(self.depth(root.left),self.depth(root.right)) + 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):
    
    is_stop = False     # 为了加快计算速度, 标志是否已经有结果了
    
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """

        def get_depth_and_balance(root):
            if self.is_stop:        # 已经是非平衡二叉树, 就不需要再计算
                return 0, False

            if not root:
                return 0, True
            if not root.left and not root.right:
                return 1, True

            ldep, l_is_balanced = get_depth_and_balance(root.left)
            rdep, r_is_balanced = get_depth_and_balance(root.right)
            
            depth = max(ldep, rdep) + 1
            is_balanced = abs(ldep- rdep) <= 1 and l_is_balanced and r_is_balanced
            
            if not is_balanced:
                self.is_stop = True
            return depth, is_balanced
        
        depth, is_balanced = get_depth_and_balance(root)
        return is_balanced

非递归版本（别人）
前序遍历

class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        stack, node = [], root
        depths = {}
        last = None
        while stack or node:
            while node:
                stack.append(node)
                node = node.left
                
            node = stack[-1]
            if not node.right or last == node.right:
                node = stack.pop()
                left, right = depths.get(node.left, 0), depths.get(node.right, 0)
                if abs(left-right) > 1: return False
                depths[node] = max(left, right) + 1
                last = node
                node = None
            else:
                node = node.right
        return True

golang版本

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func isBalanced(root *TreeNode) bool {
  return dfs(root) != -1
}

func dfs(root *TreeNode) int {
  if root == nil {
    return 0
  }
  lh := dfs(root.Left)
  if lh == -1 {
    return -1
  }
  rh := dfs(root.Right)
  if rh == -1 {
    return -1
  }
  if int(math.Abs(float64(lh-rh))) > 1 {
    return -1
  }
  return max(lh, rh)+1
}

总结：

勤思考。
小括号（）、中括号[]、花括号{}；其作用也不相同，分别用来代表不同的Python基本内置数据类型，tuple，list，dist。
D.get(key, 0) #同dict[key]，多了个没有则返回缺省值，0。[]没有则抛异常

结语

不管怎么样好好加油。

CATALOG
    FEATURED TAGS
    Blog