{"id":55,"date":"2017-09-03T02:57:03","date_gmt":"2017-09-03T09:57:03","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=55"},"modified":"2018-08-28T23:32:39","modified_gmt":"2018-08-29T06:32:39","slug":"leetcode-110-balanced-binary-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/leetcode\/leetcode-110-balanced-binary-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 110. Balanced Binary Tree"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"LeetCode 110. Balanced Binary Tree - \u82b1\u82b1\u9171 \u5237\u9898\u627e\u5de5\u4f5c  EP30\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/C75oWiy0bWM?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p>Solution 1: O(nlogn)<\/p>\n<pre class=\"lang:default decode:true\">\/\/ Author: Huahua\r\n\/\/ O(nlogn)\r\nclass Solution {\r\nSolution 1: O(nlogn)\r\npublic:\r\n    bool isBalanced(TreeNode* root) {\r\n        if(!root) return true;\r\n        int left_height = height(root-&gt;left);\r\n        int right_height = height(root-&gt;right);\r\n        return (abs(left_height - right_height)&lt;=1) &amp;&amp; isBalanced(root-&gt;left) &amp;&amp; isBalanced(root-&gt;right);\r\n    }\r\nprivate:\r\n    int height(TreeNode* root) {\r\n        if(!root) return 0;\r\n        return max(height(root-&gt;left), height(root-&gt;right))+1;\r\n    }\r\n};<\/pre>\n<p>Solution 2: O(n)<\/p>\n<pre class=\"lang:default decode:true\">\/\/ Author: Huahua\r\n\/\/ O(n)\r\nclass Solution {\r\npublic:\r\n    bool isBalanced(TreeNode* root) {\r\n        if(!root) return true;\r\n        bool balanced = true;\r\n        height(root, &amp;balanced);\r\n        return balanced;\r\n    }\r\nprivate:\r\n    int height(TreeNode* root, bool* balanced) {\r\n        if(!root) return 0;\r\n        int left_height = height(root-&gt;left, balanced);\r\n        if(!balanced) return -1;\r\n        int right_height = height(root-&gt;right, balanced);\r\n        if(!balanced) return -1;\r\n        if(abs(left_height-right_height)&gt;1) {\r\n            *balanced = false;\r\n            return -1;\r\n        }\r\n        return max(left_height, right_height) + 1;\r\n    }\r\n};<\/pre>\n<p>Java<\/p>\n<pre class=\"lang:java decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 1 ms\r\nclass Solution {\r\n  private boolean balanced;\r\n  \r\n  private int height(TreeNode root) {\r\n    if (root == null || !this.balanced) return -1;\r\n    int l = height(root.left);\r\n    int r = height(root.right);\r\n    if (Math.abs(l - r) &gt; 1) {\r\n      this.balanced = false;\r\n      return -1;\r\n    }\r\n    return Math.max(l, r) + 1;\r\n  }\r\n  \r\n  public boolean isBalanced(TreeNode root) {\r\n    this.balanced = true;\r\n    height(root);\r\n    return this.balanced;\r\n  }\r\n}<\/pre>\n<p>&nbsp;<\/p>\n<p>Python<\/p>\n<pre class=\"lang:python decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 76 ms\r\n\"\"\"\r\nclass Solution:\r\n  def isBalanced(self, root):\r\n    self.balanced = True\r\n    def height(root):\r\n      if not root or not self.balanced: return -1\r\n      l = height(root.left)\r\n      r = height(root.right)\r\n      if abs(l - r) &gt; 1:\r\n        self.balanced = False\r\n        return -1\r\n      return max(l, r) + 1\r\n    height(root)\r\n    return self.balanced<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Solution 1: O(nlogn) \/\/ Author: Huahua \/\/ O(nlogn) class Solution { Solution 1: O(nlogn) public: bool isBalanced(TreeNode* root) { if(!root) return true; int left_height =&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,45],"tags":[30],"class_list":["post-55","post","type-post","status-publish","format-standard","hentry","category-leetcode","category-tree","tag-binary-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/55","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=55"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/55\/revisions"}],"predecessor-version":[{"id":3747,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/55\/revisions\/3747"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=55"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=55"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=55"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}