【剑指Offer】039——平衡二叉树（树）

题目

输入一棵二叉树，判断该二叉树是否是平衡二叉树

思路

平衡二叉树：某节点的左右子树深度差绝对值不超过1。利用递归求左右子树的深度，以判断这颗树是不是平衡的。

参考代码

import java.util.HashMap;
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) return true;
        int left = deep(root.left); // 获取左子树深度
        int right = deep(root.right);// 获取右子树深度
        int diff = left - right;
        if (diff > 1 || diff < -1) return false;
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
    public int deep(TreeNode root){
        if (root == null) return 0;
        int left = deep(root.left); // 获取左子树的深度
        int right = deep(root.right); // 获取右子树的深度
        return left > right ? left + 1:right + 1;
    }
}

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here
        if not pRoot:return True
        left = self.deep(pRoot.left)
        right = self.deep(pRoot.right)
        diff = left - right
        if diff > 1 or diff < -1: return False 
        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
    def deep(self, root):
        if not root :return 0
        left = self.deep(root.left)
        right = self.deep(root.right)
        return left + 1 if left > right else right + 1

个人订阅号

image