題目：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.

?

個人思路：

1、判斷每個節點（子樹）的高度差，高度差在絕對值為1的范圍內便是平衡二叉樹

2、可以適當改造計算樹高度的方法，即樹的高度為左子樹與右子樹高度較大者加1

?

代碼：

1 #include <stddef.h> 2 #include <iostream> 3 /** 4 * Definition for binary tree 5 * struct TreeNode { 6 * int val; 7 * TreeNode *left; 8 * TreeNode *right; 9 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 10 * }; 11 */ 12 13 struct TreeNode 14 { 15 int val; 16 TreeNode *left; 17 TreeNode *right; 18 TreeNode(int x) : val(x), left(NULL), right(NULL) {} 19 }; 20 21 class Solution 22 { 23 public: 24 bool isBalanced(TreeNode *root) 25 { 26 balanced = true; 27 getDepth(root); 28 29 return balanced; 30 } 31 int getDepth(TreeNode *root) 32 { 33 if (root == NULL) 34 { 35 return 0; 36 } 37 38 int leftDepth = getDepth(root->left); 39 int rightDepth = getDepth(root->right); 40 41 if (leftDepth - rightDepth > 1 || leftDepth - rightDepth < -1) 42 { 43 balanced = false; 44 } 45 46 return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1; 47 } 48 private: 49 bool balanced; 50 }; 51 52 int main() 53 { 54 TreeNode *root = new TreeNode(1); 55 root->right = new TreeNode(1); 56 root->right->right = new TreeNode(1); 57 Solution s; 58 s.isBalanced(root); 59 std::cout << root->val << std::endl << root->right->val << std::endl << root->right->val << std::endl; 60 system("pause"); 61 62 return 0; 63 } View Code

?

?上網搜了一些帖子，方法都是類似，就不貼出來了

轉載于:https://www.cnblogs.com/laihaiteng/p/3795408.html

總結

以上是生活随笔為你收集整理的leetcode - Balanced Binary Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。