剑指offer----平衡二叉树

剑指offer----平衡二叉树

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

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution { //返回以root为根的树的最长深度 int lenth_tree(TreeNode* pRoot) { if(pRoot==NULL)return 0; return max(lenth_tree(pRoot->left),lenth_tree(pRoot->right))+1; }public: //判断以pRoot为根的树是否是平衡二叉树 bool isBalanced(TreeNode* pRoot) { if(pRoot==NULL)return true; //当前根节点的左右孩子的深度超过1，返回为false if(abs(lenth_tree(pRoot->left)-lenth_tree(pRoot->right))>1) return false; else //当前根节点的左右孩子深度不超过1，且以左右孩子为根的二叉树都是平衡二叉树 return isBalanced(pRoot->left)&&isBalanced(pRoot->right); }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。