You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
<
7377
script type="application/json" data-target="react-app.embeddedData">{"payload":{"allShortcutsEnabled":false,"path":"109. Balanced Binary Tree","repo":{"id":490101071,"defaultBranch":"master","name":"LeetCode","ownerLogin":"algorithms-forks","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2022-05-09T01:47:36.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/105182575?v=4","public":true,"private":false,"isOrgOwned":true},"currentUser":null,"refInfo":{"name":"master","listCacheKey":"v0:1652060858.178429","canEdit":false,"refType":"branch","currentOid":"1756256d7e619164076bbf358c8f7ca68cd8bd79"},"tree":{"items":[{"name":"README.md","path":"109. Balanced Binary Tree/README.md","contentType":"file"},{"name":"main.cc","path":"109. Balanced Binary Tree/main.cc","contentType":"file"},{"name":"solution.h","path":"109. Balanced Binary Tree/solution.h","contentType":"file"}],"templateDirectorySuggestionUrl":null,"readme":{"displayName":"README.md","richText":"\u003carticle class=\"markdown-body entry-content container-lg\" itemprop=\"text\"\u003e\u003cp dir=\"auto\"\u003e这道题,我昨天就在想了。毕竟平衡搜索树只不过是特殊的平衡二叉树罢了。是否平衡的关键在于题目里给出的这个定义:\u003c/p\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003ea 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.\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cp dir=\"auto\"\u003e所以这个问题很重要的一个子问题就是:如何求二叉树的高度。假设我们找到了高度的方法,那么核心判断就是:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-c++ notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"std::abs(height(root-\u0026gt;left), height(root-\u0026gt;right)) \u0026lt;= 1\"\u003e\u003cpre\u003e\u003cspan class=\"pl-en\"\u003estd::abs\u003c/span\u003e(height(root-\u0026gt;left), height(root-\u0026gt;right)) \u0026lt;= 1\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e所以我几乎是瞬间写出了\u003ca href=\"/algorithms-forks/LeetCode/blob/e6906ef932bda154ad17518e6d097c904045048f/22.%20Balanced%20Binary%20Tree/solution.h#L22-L32\"\u003e解决方法\u003c/a\u003e(递归真的是人类自然而然的思路呀)。\n但往往自然的思路,有时会伴随着效率低下,虽然被 LeetCode 认可了的(可AC)。\u003c/p\u003e\n\u003chr\u003e\n\u003cp dir=\"auto\"\u003e于是我尝试缩减递归次数,能想到的办法就是及早的判断出非平衡,然后跳出递归。那么又回到上面的\u003cstrong\u003e判断核心\u003c/strong\u003e上,只要那个条件不成立,我就应该跳出递归。可是如何能跳出递归呢?\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e我能想到的方法就是设一个 bool 成员变量,然后一旦为 false, 立刻停止。这就是目前我的方案了。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e希望抛砖引玉,了解更多的方案。\u003c/p\u003e\n\u003chr\u003e\n\u003cp dir=\"auto\"\u003e最近持续不断的做有关 \u003cstrong\u003etree\u003c/strong\u003e 的题目,让我深深感觉到,在树算法中,不用递归简直是找死,自建栈也好,自建队列也好,\n都要维护一大堆东西,在效率上不仅没有显著的提升,反而让程序晦涩难懂,表意不明。如何抉择呢?我一定还是偏向于使用递归的。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e在效率没有明显提升的情况下,递归表达意图的能力,实在是让人无法割舍。\u003c/p\u003e\n\u003c/article\u003e","errorMessage":null,"headerInfo":{"toc":[],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Falgorithms-forks%2FLeetCode%2Ftree%2Fmaster%2F109.%2520Balanced%2520Binary%2520Tree"}},"totalCount":3,"showBranchInfobar":true},"fileTree":{"":{"items":[{"name":"000. Two Sum","path":"000. Two Sum","contentType":"directory"},{"name":"001. Add Two Numbers","path":"001. Add Two Numbers","contentType":"directory"},{"name":"002. Longest Substring Without Repeating Characters","path":"002. Longest Substring Without Repeating Characters","contentType":"directory"},{"name":"004. Longest Palindromic Substring","path":"004. Longest Palindromic Substring","contentType":"directory"},{"name":"005. ZigZag Conversion","path":"005. ZigZag Conversion","contentType":"directory"},{"name":"006. Reverse Integer","path":"006. Reverse Integer","contentType":"directory"},{"name":"007. Linked List Cycle","path":"007. Linked List Cycle","contentType":"directory"},{"name":"008. Palindrome Number","path":"008. Palindrome Number","contentType":"directory"},{"name":"009. Regular Expression Matching","path":"009. Regular Expression Matching","contentType":"directory"},{"name":"010. Container With Most Water","path":"010. Container With Most Water","contentType":"directory"},{"name":"011. Integer to Roman","path":"011. Integer to Roman","contentType":"directory"},{"name":"012. Roman to Integer","path":"012. Roman to Integer","contentType":"directory"},{"name":"013. Longest Common Prefix","path":"013. Longest Common Prefix","contentType":"directory"},{"name":"015. 3Sum Closest","path":"015. 3Sum Closest","contentType":"directory"},{"name":"016. Letter Combinations of a Phone Number","path":"016. Letter Combinations of a Phone Number","contentType":"directory"},{"name":"017. 4Sum","path":"017. 4Sum","contentType":"directory"},{"name":"018. Remove Nth Node from End of List","path":"018. Remove Nth Node from End of List","contentType":"directory"},{"name":"019. Valid Parentheses","path":"019. Valid Parentheses","contentType":"directory"},{"name":"020. Merge Two Sorted Lists","path":"020. Merge Two Sorted Lists","contentType":"directory"},{"name":"021. Generate Parentheses","path":"021. Generate Parentheses","contentType":"directory"},{"name":"022. Merge k Sorted Lists","path":"022. Merge k Sorted Lists","contentType":"directory"},{"name":"023. Swap Nodes in Pairs","path":"023. Swap Nodes in Pairs","contentType":"directory"},{"name":"024. Reverse Nodes in k-Group","path":"024. Reverse Nodes in k-Group","contentType":"directory"},{"name":"025. Remove Duplicates from Sorted Array","path":"025. Remove Duplicates from Sorted Array","contentType":"directory"},{"name":"026. Remove Element","path":"026. Remove Element","contentType":"directory"},{"name":"027. Implement strStr()","path":"027. Implement strStr()","contentType":"directory"},{"name":"030. Next Permutation","path":"030. Next Permutation","contentType":"directory"},{"name":"032. Search in Rotated Sorted Array","path":"032. Search in Rotated Sorted Array","contentType":"directory"},{"name":"033. Search for a Range","path":"033. Search for a Range","contentType":"directory"},{"name":"034. Search Insert Position","path":"034. Search Insert Position","contentType":"directory"},{"name":"035. Valid Sudoku","path":"035. Valid Sudoku","contentType":"directory"},{"name":"036. Sudoku Solver","path":"036. Sudoku Solver","contentType":"directory"},{"name":"037. Count and Say","path":"037. Count and Say","contentType":"directory"},{"name":"038. Combination Sum","path":"038. Combination Sum","contentType":"directory"},{"name":"039. Combination Sum II","path":"039. Combination Sum II","contentType":"directory"},{"name":"040. First Missing Positive","path":"040. First Missing Positive","contentType":"directory"},{"name":"041. Trapping Rain Water","path":"041. Trapping Rain Water","contentType":"directory"},{"name":"042. Multiply Strings","path":"042. Multiply Strings","contentType":"directory"},{"name":"044. Jump Game II","path":"044. Jump Game II","contentType":"directory"},{"name":"045. Permutations","path":"045. Permutations","contentType":"directory"},{"name":"046. Permutations II","path":"046. Permutations II","contentType":"directory"},{"name":"047. Rotate Image","path":"047. Rotate Image","contentType":"directory"},{"name":"048. Group Anagrams","path":"048. Group Anagrams","contentType":"directory"},{"name":"049. Pow(x, n)","path":"049. Pow(x, n)","contentType":"directory"},{"name":"050. N-Queens","path":"050. N-Queens","contentType":"directory"},{"name":"051. N-Queens II","path":"051. N-Queens II","contentType":"directory"},{"name":"052. Maximum Subarray","path":"052. Maximum Subarray","contentType":"directory"},{"name":"053. Spiral Matrix","path":"053. Spiral Matrix","contentType":"directory"},{"name":"054. Jump Game","path":"054. Jump Game","contentType":"directory"},{"name":"055. Merge Intervals","path":"055. Merge Intervals","contentType":"directory"},{"name":"056. Insert Interval","path":"056. Insert Interval","contentType":"directory"},{"name":"057. Length of Last Word","path":"057. Length of Last Word","contentType":"directory"},{"name":"058. Spiral Matrix II","path":"058. Spiral Matrix II","contentType":"directory"},{"name":"059. Permutation Sequence","path":"059. Permutation Sequence","contentType":"directory"},{"name":"060. Rotate List","path":"060. Rotate List","contentType":"directory"},{"name":"061. Unique Paths","path":"061. Unique Paths","contentType":"directory"},{"name":"062. Unique Paths II","path":"062. Unique Paths II","contentType":"directory"},{"name":"063. Minimum Path Sum","path":"063. Minimum Path Sum","contentType":"directory"},{"name":"065. Plus One","path":"065. Plus One","contentType":"directory"},{"name":"066. Add Binary","path":"066. Add Binary","contentType":"directory"},{"name":"068. Sqrt(x)","path":"068. Sqrt(x)","contentType":"directory"},{"name":"069. Climbing Stairs","path":"069. Climbing Stairs","contentType":"directory"},{"name":"070. Simplify Path","path":"070. Simplify Path","contentType":"directory"},{"name":"071. Edit Distance","path":"071. Edit Distance","contentType":"directory"},{"name":"072. Set Matrix Zeroes","path":"072. Set Matrix Zeroes","contentType":"directory"},{"name":"073. Search a 2D Matrix","path":"073. Search a 2D Matrix","contentType":"directory"},{"name":"074. Sort Colors","path":"074. Sort Colors","contentType":"directory"},{"name":"076. Combinations","path":"076. Combinations","contentType":"directory"},{"name":"077. Subsets","path":"077. Subsets","contentType":"directory"},{"name":"079. Remove Duplicates from Sorted Array II","path":"079. Remove Duplicates from Sorted Array II","contentType":"directory"},{"name":"080. Search in Rotated Sorted Array II","path":"080. Search in Rotated Sorted Array II","contentType":"directory"},{"name":"081. Remove Duplicates from Sorted List II","path":"081. Remove Duplicates from Sorted List II","contentType":"directory"},{"name":"082. Remove Duplicates from Sorted List","path":"082. Remove Duplicates from Sorted List","contentType":"directory"},{"name":"083. Largest Rectangle in Histogram","path":"083. Largest Rectangle in Histogram","contentType":"directory"},{"name":"084. Maximal Rectangle","path":"084. Maximal Rectangle","contentType":"directory"},{"name":"085. Partition List","path":"085. Partition List","contentType":"directory"},{"name":"086. Scramble String","path":"086. Scramble String","contentType":"directory"},{"name":"087. Merge Sorted Array","path":"087. Merge Sorted Array","contentType":"directory"},{"name":"088. Gray Code","path":"088. Gray Code","contentType":"directory"},{"name":"089. Subsets II","path":"089. Subsets II","contentType":"directory"},{"name":"090. Insertion Sort List","path":"090. Insertion Sort List","contentType":"directory"},{"name":"091. Reverse Linked List II","path":"091. Reverse Linked List II","contentType":"directory"},{"name":"092. Restore IP Addresses","path":"092. Restore IP Addresses","contentType":"directory"},{"name":"093. Binary Tree Inorder Traversal","path":"093. Binary Tree Inorder Traversal","contentType":"directory"},{"name":"094. Unique Binary Search Trees II","path":"094. Unique Binary Search Trees II","contentType":"directory"},{"name":"095. Unique Binary Search Trees","path":"095. Unique Binary Search Trees","contentType":"directory"},{"name":"097. Validate Binary Search Tree","path":"097. Validate Binary Search Tree","contentType":"directory"},{"name":"098. Recover Binary Search Tree","path":"098. Recover Binary Search Tree","contentType":"directory"},{"name":"099. Same Tree","path":"099. Same Tree","contentType":"directory"},{"name":"100. Symmetric Tree","path":"100. Symmetric Tree","contentType":"directory"},{"name":"101. Binary Tree Level Order Traversal","path":"101. Binary Tree Level Order Traversal","contentType":"directory"},{"name":"102. Binary Tree Zigzag Level Order Traversal","path":"102. Binary Tree Zigzag Level Order Traversal","contentType":"directory"},{"name":"103. Maximum Depth of Binary Tree","path":"103. Maximum Depth of Binary Tree","contentType":"directory"},{"name":"104. Construct Binary Tree from Preorder and Inorder Traversal","path":"104. Construct Binary Tree from Preorder and Inorder Traversal","contentType":"directory"},{"name":"105. Construct Binary Tree from Inorder and Postorder Traversal","path":"105. Construct Binary Tree from Inorder and Postorder Traversal","contentType":"directory"},{"name":"106. Binary Tree Level Order Traversal II","path":"106. Binary Tree Level Order Traversal II","contentType":"directory"},{"name":"107. Convert Sorted Array to Binary Search Tree","path":"107. Convert Sorted Array to Binary Search Tree","contentType":"directory"},{"name":"108. Convert Sorted List to Binary Search Tree","path":"108. Convert Sorted List to Binary Search Tree","contentType":"directory"},{"name":"109. Balanced Binary Tree","path":"109. Balanced Binary Tree","contentType":"directory"},{"name":"110. Minimum Depth of Binary Tree","path":"110. Minimum Depth of Binary Tree","contentType":"directory"},{"name":"111. Path Sum","path":"111. Path Sum","contentType":"directory"},{"name":"112. Path Sum II","path":"112. Path Sum II","contentType":"directory"},{"name":"113. Flatten Binary Tree to Linked List","path":"113. Flatten Binary Tree to Linked List","contentType":"directory"},{"name":"114. Distinct Subsequences","path":"114. Distinct Subsequences","contentType":"directory"},{"name":"115. Populating Next Right Pointers in Each Node","path":"115. Populating Next Right Pointers in Each Node","contentType":"directory"},{"name":"116. Populating Next Right Pointers in Each Node II","path":"116. Populating Next Right Pointers in Each Node II","contentType":"directory"},{"name":"117. Pascal's Triangle","path":"117. Pascal's Triangle","contentType":"directory"},{"name":"118. Pascal's Triangle II","path":"118. Pascal's Triangle II","contentType":"directory"},{"name":"119. Triangle","path":"119. Triangle","contentType":"directory"},{"name":"120. Best Time to Buy and Sell Stock","path":"120. Best Time to Buy and Sell Stock","contentType":"directory"},{"name":"121. Best Time to Buy and Sell Stock II","path":"121. Best Time to Buy and Sell Stock II","contentType":"directory"},{"name":"122. Best Time to Buy and Sell Stock III","path":"122. Best Time to Buy and Sell Stock III","contentType":"directory"},{"name":"122. Sort List","path":"122. Sort List","contentType":"directory"},{"name":"123. Binary Tree Maximum Path Sum","path":"123. Binary Tree Maximum Path Sum","contentType":"directory"},{"name":"124. Valid Palindrome","path":"124. Valid Palindrome","contentType":"directory"},{"name":"125. Reorder List","path":"125. Reorder List","contentType":"directory"},{"name":"127. Longest Consecutive Sequence","path":"127. Longest Consecutive Sequence","contentType":"directory"},{"name":"128. Sum Root to Leaf Numbers","path":"128. Sum Root to Leaf Numbers","contentType":"directory"},{"name":"130. Palindrome Partitioning","path":"130. Palindrome Partitioning","contentType":"directory"},{"name":"132. Clone Graph","path":"132. Clone Graph","contentType":"directory"},{"name":"133. Gas Station","path":"133. Gas Station","contentType":"directory"},{"name":"135. Single Number","path":"135. Single Number","contentType":"directory"},{"name":"136. Single Number II","path":"136. Single Number II","contentType":"directory"},{"name":"137. Copy List with Random Pointer","path":"137. Copy List with Random Pointer","contentType":"directory"},{"name":"138. Word Break","path":"138. Word Break","contentType":"directory"},{"name":"141. Linked List Cycle II","path":"141. Linked List Cycle II","contentType":"directory"},{"name":"143. Binary Tree Preorder Traversal","path":"143. Binary Tree Preorder Traversal","contentType":"directory"},{"name":"144. Binary Tree Postorder Traversal","path":"144. Binary Tree Postorder Traversal","contentType":"directory"},{"name":"152. Find Minimum in Rotated Sorted Array","path":"152. Find Minimum in Rotated Sorted Array","contentType":"directory"},{"name":"435. Find All Duplicates in an Array","path":"435. Find All Duplicates in an Array","contentType":"directory"},{"name":"619. Maximum Average Subarray I","path":"619. Maximum Average Subarray I","contentType":"directory"},{"name":"630. Maximum Binary Tree","path":"630. Maximum Binary Tree","contentType":"directory"},{"name":"Catch","path":"Catch","contentType":"submodule","submoduleUrl":"/catchorg/Catch2/tree/d4e5f184369ce34592bb6f89e793bdb22d1d011a","submoduleDisplayName":"Catch @ d4e5f18"},{"name":".gitignore","path":".gitignore","contentType":"file"},{"name":".gitmodules","path":".gitmodules","contentType":"file"},{"name":"LICENSE","path":"LICENSE","contentType":"file"},{"name":"README.md","path":"README.md","contentType":"file"}],"totalCount":137}},"fileTreeProcessingTime":7.294836,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/algorithms-forks/LeetCode/branches":{"post":"DTxPMZoDZIm7F5QCXhfWh0WMZxVrJE_wzNm8f1BTDFEryQg8Kml-mhDXDz9Zs5elnADXHI8skAeGgWVPyUnD6w"},"/algorithms-forks/LeetCode/branches/fetch_and_merge/master":{"post":"ADGeAcgQiOXryZnW9raznX5m2bRgSdXEVcjsxjDvAOlr8xeygPmOrR_q2RN9goYfCit3el96aM6yTZjuGEua8Q"},"/algorithms-forks/LeetCode/branches/fetch_and_merge/master?discard_changes=true":{"post":"TsZhPiNH5EpYUmLA6qXePMpSsA7ezEfRD_GWi_ddpMwlBOiNa67iAqxxIgVhkeu-vh8ewOH_-tvodOKj3_k-1A"}}},"title":"LeetCode/109. Balanced Binary Tree at master · algorithms-forks/LeetCode","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-263cab1760dd.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-1b17b3e7786a.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true}}}