美文网首页
二叉树的深度、二叉平衡树

二叉树的深度、二叉平衡树

作者: fighting_css | 来源:发表于2018-08-29 11:36 被阅读0次

【题目】
输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
思路:
递归调用
case1:当前节点有左右子树,则树的深度为左右子树最大值加1
case2:当前节点只有右子树,则树的深度为左子树加1
case3:当前节点只有左子树,则树的深度为右子树加1
递归出口:
树为空,return 0
当前节点为叶节点:
return 1
代码:

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        #递归
        if pRoot==None:
            return 0
        if pRoot.left==None and pRoot.right==None:
            return 1
        #左右子树都不为空
        if pRoot.left!=None and pRoot.right!=None:
            return max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right))+1
        #右子树为空
        elif pRoot.right==None:
            return self.TreeDepth(pRoot.left)+1
        #左子树为空
        else:
            return self.TreeDepth(pRoot.right)+1

调用树的深度函数,递归判断左右子树是否都满足高度差不超过1
代码:

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        #递归
        if pRoot==None:
            return 0
        if pRoot.left==None and pRoot.right==None:
            return 1
        #左右子树都不为空
        if pRoot.left!=None and pRoot.right!=None:
            return max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right))+1
        #右子树为空
        elif pRoot.right==None:
            return self.TreeDepth(pRoot.left)+1
        #左子树为空
        else:
            return self.TreeDepth(pRoot.right)+1
    def IsBalanced_Solution(self, pRoot):
        # write code here
        if pRoot == None:
            return True
        if abs(self.TreeDepth(pRoot.left)-self.TreeDepth(pRoot.right))>1:
            return False
        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
        return True

相关文章

  • 面试题55 - II. 平衡二叉树

    平衡二叉树 题目描述 输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差...

  • 二叉树的深度和平衡二叉树(LeetCode 剑指Offer 55

    题目 输入一棵二叉树的根节点,求该树的深度。输入一棵二叉树的根节点,判断该树是不是平衡二叉树。 二叉树的深度 解析...

  • 判断平衡二叉树——Python

    给定一棵二叉树,判断它是否为平衡二叉树。 平衡二叉树的定义是:如果某二叉树中任意节点的左右子树的深度相差不超过1,...

  • 【剑指Offer】039——平衡二叉树(树)

    题目 输入一棵二叉树,判断该二叉树是否是平衡二叉树 思路 平衡二叉树:某节点的左右子树深度差绝对值不超过1。利用递...

  • 平衡二叉树(AVL)

    定义 平衡二叉树是建立在二叉平衡树基础上,目的使得各个节点的深度尽可能小。平衡二叉树是一颗二叉树,或者为空,或者满...

  • LeetCode110 平衡二叉树

    题目: 思路:平衡二叉树的条件:1.左子树是平衡二叉树2.右子树是平衡二叉树3.左右子树之间的深度不超过1 代码实现:

  • 二叉树笔试面试题集合

    二叉树深度 判断平衡二叉树 一种方法 可以利用求二叉树深度,从根节点开始递归。再求左右深度进行比较。最后求到叶子节...

  • 判断一个树是否是BST 求一棵平衡二叉树的最小深度 判断一棵二叉树是否高度平衡

  • 判断二叉树是否平衡

    子树 平衡二叉树 判断是否为平衡二叉树 在遍历树的每个结点的时候,调用函数TreeDepth得到它的左右子树的深度...

  • 剑指 offer:39、平衡二叉树

    39. 平衡二叉树 题目描述 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 解题思路: 平衡二叉树:Wiki:在...

网友评论

      本文标题:二叉树的深度、二叉平衡树

      本文链接:https://www.haomeiwen.com/subject/ajphwftx.html