首页 > 代码库 > Balanced Binary Tree （二叉树DFS）
Balanced Binary Tree （二叉树DFS）
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
判断一棵树是否为平衡二叉树。
思路：典型的递归，从第一个根节点开始，看左子树和右子树的深度差值是否小于等于1，然后再看由根节点的左孩子和右孩子构成的两课树是否都符合条件。
代码：
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {private: int maxdepth;public: void solve(TreeNode *root,int depth){ if(root==NULL) return; if(depth>maxdepth) maxdepth=depth; solve(root->left,depth+1); solve(root->right,depth+1); } int getDepth(TreeNode *root) { maxdepth=0; solve(root,1); return maxdepth; } bool isBalanced(TreeNode *root) { if(root==NULL) return true; int l,r; if(root->left!=NULL){ l=getDepth(root->left); }else{ l=0; } if(root->right!=NULL){ r=getDepth(root->right); }else{ r=0; } return abs(l-r)<=1&&isBalanced(root->left)&&isBalanced(root->right); }};
Balanced Binary Tree （二叉树DFS）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。