平衡二叉树检查 牛客网 程序员面试金典 C++ Python

平衡二叉树检查 牛客网 程序员面试金典 C++ Python

题目描述

实现一个函数，检查二叉树是否平衡，平衡的定义如下，对于树中的任意一个结点，其两颗子树的高度差不超过1。

给定指向树根结点的指针TreeNode* root，请返回一个bool，代表这棵树是否平衡。

C++

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Balance { public: //rum:3ms memory:408k bool isBalance(TreeNode* root) { if (NULL == root) return true; if (NULL == root->left && NULL == root->right) return true; if (NULL != root->left && NULL == root->right) if(getTreeHeight(root->left) > 1) return false; if (NULL == root->left && NULL != root->right) if(getTreeHeight(root->right) >1) return false; return isBalance(root->left) && isBalance(root->right); } int getTreeHeight(TreeNode* root){ if (NULL == root) return 0; return max(getTreeHeight(root->left),getTreeHeight(root->right))+ 1; } };

Python

# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Balance: #run:27ms memory:5736k def isBalance(self, root): if None == root: return True if None == root.left and None == root.right: return True if None != root.left and None == root.right: if self.getTreeHeight(root.left) > 1: return False if None == root.left and None != root.right: if self.getTreeHeight(root.right) > 1:return False return self.isBalance(root.left) and self.isBalance(root.right) + 1 def getTreeHeight(self,root): if None == root: return 0 return max(self.getTreeHeight(root.left),self.getTreeHeight(root.right)) + 1

 

转载于:https://www.cnblogs.com/vercont/p/10210322.html

相关资源：JAVA上百实例源码以及开源项目