[[426529]]

本文轉(zhuǎn)載自微信公眾號(hào)「三分鐘學(xué)前端」，作者sisterAn  。轉(zhuǎn)載本文請(qǐng)聯(lián)系三分鐘學(xué)前端公眾號(hào)。

關(guān)于樹(shù)基礎(chǔ)看這里：適合初學(xué)者的樹(shù)

給定一個(gè)二叉樹(shù)，判斷它是否是高度平衡的二叉樹(shù)。

本題中，一棵高度平衡二叉樹(shù)定義為：

一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1。

示例 1:

給定二叉樹(shù) [3,9,20,null,null,15,7]

  3 
 / \ 
9  20 
  /  \ 
 15   7 

返回 true 。

示例 2:

給定二叉樹(shù) [1,2,2,3,3,null,null,4,4]

    1 
     / \ 
    2   2 
   / \ 
  3   3 
 / \ 
4   4 

返回 false 。

解答一：自頂向下(暴力法)

解題思路： 自頂向下的比較每個(gè)節(jié)點(diǎn)的左右子樹(shù)的最大高度差，如果二叉樹(shù)中每個(gè)節(jié)點(diǎn)的左右子樹(shù)最大高度差小于等于 1 ，即每個(gè)子樹(shù)都平衡時(shí)，此時(shí)二叉樹(shù)才是平衡二叉樹(shù)

代碼實(shí)現(xiàn)：

const isBalanced = function (root) { 
  if(!root) return true 
  return Math.abs(depth(root.left) - depth(root.right)) <= 1 
        && isBalanced(root.left) 
        && isBalanced(root.right) 
} 
const depth = function (node) { 
    if(!node) return -1 
    return 1 + Math.max(depth(node.left), depth(node.right)) 
} 

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(nlogn)，計(jì)算 depth 存在大量冗余操作
• 空間復(fù)雜度：O(n)

解答二：自底向上(優(yōu)化)

解題思路： 利用后續(xù)遍歷二叉樹(shù)(左右根)，從底至頂返回子樹(shù)最大高度，判定每個(gè)子樹(shù)是不是平衡樹(shù) ，如果平衡，則使用它們的高度判斷父節(jié)點(diǎn)是否平衡，并計(jì)算父節(jié)點(diǎn)的高度，如果不平衡，返回 -1 。

遍歷比較二叉樹(shù)每個(gè)節(jié)點(diǎn) 的左右子樹(shù)深度：

• 比較左右子樹(shù)的深度，若差值大于 1 則返回一個(gè)標(biāo)記 -1 ，表示當(dāng)前子樹(shù)不平衡
• 左右子樹(shù)有一個(gè)不是平衡的，或左右子樹(shù)差值大于 1 ，則二叉樹(shù)不平衡
• 若左右子樹(shù)平衡，返回當(dāng)前樹(shù)的深度(左右子樹(shù)的深度最大值 +1 )

代碼實(shí)現(xiàn)：

const isBalanced = function (root) { 
    return balanced(root) !== -1 
}; 
const balanced = function (node) { 
    if (!node) return 0 
    const left = balanced(node.left) 
    const right = balanced(node.right) 
    if (left === -1 || right === -1 || Math.abs(left - right) > 1) { 
        return -1 
    } 
    return Math.max(left, right) + 1 
} 

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)