首页 > 代码库 > Balanced Binary Tree
Balanced Binary Tree
Balanced Binary Tree
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.
C++版本1：
#include <iostream>#include <vector>#include <stdlib.h>using namespace std;struct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int x):val(x),right(NULL),left(NULL){}};class Solution{private: bool balanced=true; int height(TreeNode *root){ if(!balanced){ return -1; } if(root==NULL){ return 0; } int leftH,rightH; leftH=height(root->left)+1; rightH=height(root->right)+1; if(abs(leftH-rightH)>1){ balanced=false; } return leftH>rightH?leftH:rightH; } bool isBalanced(TreeNode *root){ balanced=true; height(root); return balanced; }};int main(){ cout << "Hello world!" << endl; return 0;}c++版本2：
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: bool checkBalance(TreeNode *node, int &dep) { if (node == NULL) { dep = 0; return true; } int leftDep, rightDep; bool leftBalance = checkBalance(node->left, leftDep); bool rightBalance = checkBalance(node->right, rightDep); dep = max(leftDep, rightDep)+1; return leftBalance && rightBalance && (abs(rightDep - leftDep) <= 1); } bool isBalanced(TreeNode *root) { // Start typing your C/C++ solution below // DO NOT write int main() function int dep; return checkBalance(root, dep); }};Java版本：
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public boolean isBalanced(TreeNode root) { if (root == null) return true; if (getHeight(root) == -1) return false; return true; } public int getHeight(TreeNode root) { if (root == null) return 0; int left = getHeight(root.left); int right = getHeight(root.right); if (left == -1 || right == -1) return -1; if (Math.abs(left - right) > 1) { return -1; } return Math.max(left, right) + 1; }}
Balanced Binary Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。