前言

今天說說二叉樹。

樹

首先看看什么是樹??。

如圖，這種有節(jié)點的結(jié)構(gòu)就是樹。

樹 是n(n>=0)個結(jié)點的有限集

其中：

• 每個元素叫做 節(jié)點
• 上一節(jié)是下一節(jié)的 父節(jié)點，比如1是2的父節(jié)點
• 最上面的節(jié)點，也就是沒有父節(jié)點的節(jié)點叫做 根節(jié)點，比如1
• 同一個父節(jié)點的節(jié)點叫做 兄弟節(jié)點，比如2、3、4是兄弟節(jié)點
• 沒有子節(jié)點的節(jié)點叫做 葉子節(jié)點

二叉樹

聽名字還是比較好理解的，就是每個節(jié)點有兩個分叉的樹。但是又不要求一定有兩個節(jié)點，只要小于等于2個節(jié)點就可以。

比如這種：

其中，可以看到綠色的樹每個節(jié)點都有左右兩個節(jié)點，這種二叉樹就叫做 滿二叉樹。

還有一種二叉樹叫做 完全二叉樹。

完全二叉樹: 對一顆具有n個結(jié)點的二叉樹按層編號，如果編號為i(1<=i<=n)的結(jié)點與同樣深度的滿二叉樹中編號為i的結(jié)點在二叉樹中位置完全相同，則這棵二叉樹稱為完全二叉樹。

啥意思呢，比如一個滿二叉樹，每個節(jié)點進行順序編號，如果去了一些節(jié)點，編號不會變化，那么就是完全二叉樹，比如：

這張圖中，綠色樹是滿二叉樹，當去掉7號節(jié)點，變成了黃色樹。

這顆黃色樹的序號相對于滿二叉樹的序號都能一一對應(yīng)，所以這個黃色樹就是完全二叉樹。

如果去掉的是6號節(jié)點，變成紅色樹，這時候，紅色樹的節(jié)點就必須有所變化了，6消失后節(jié)點7必須變成節(jié)點6才正確。

所以這個紅色樹就不是完全二叉樹，因為它相對于滿二叉樹序號有所改變，已經(jīng)對應(yīng)不上了。

算法——平衡二叉樹

說了這么多，該來個題練練手了。

輸入一棵二叉樹的根節(jié)點，判斷該樹是不是平衡二叉樹。如果某二叉樹中任意節(jié)點的左右子樹的深度相差不超過1，那么它就是一棵平衡二叉樹。

示例 1: 給定二叉樹 [3,9,20,null,null,15,7]

  3 
 / \ 
9  20 
  /  \ 
 15   7 

返回 true 。

解析

題目給出了平衡二叉樹的概念，就是任意節(jié)點的左右子樹相差不超過1，就是平衡二叉樹。

那這個深度是啥呢?

深度就是根節(jié)點到當前節(jié)點經(jīng)過的邊個數(shù)

層數(shù)就是當前節(jié)點在第幾層，跟節(jié)點為第一層，所以層數(shù)=深度+1

 1       深度 0 ，層數(shù) 1 
 / \ 
2  3      深度 1 ，層數(shù) 2 
  /  \ 
 4    5   深度 2 ，層數(shù) 3 

解法1

首先容易想到的就是把每個節(jié)點的深度都算出來，然后進行左右節(jié)點比較就能得出是不是平衡二叉樹。

那么節(jié)點的子樹深度怎么計算呢?

遞歸。當子節(jié)點為空就返回，否則每次增加一個單位深度。

/** 
 * Definition for a binary tree node. 
 * public class TreeNode { 
 *     int val; 
 *     TreeNode left; 
 *     TreeNode right; 
 *     TreeNode(int x) { val = x; } 
 * } 
 */ 
 
    private int depth(TreeNode root) { 
        if (root == null) return 0; 
        return Math.max(depth(root.left), depth(root.right)) + 1; 
    } 

深度搞定了，這題就好解了，即遍歷每個節(jié)點的左右深度，還是要 用到遞歸：

class Solution { 
    public boolean isBalanced(TreeNode root) { 
        if (root == null) return true; 
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); 
    } 
 
    private int depth(TreeNode root) { 
        if (root == null) return 0; 
        return Math.max(depth(root.left), depth(root.right)) + 1; 
    } 
} 

從根節(jié)點開始，計算每個左子樹深度和右子樹深度的差值，以及下面的每個節(jié)點的左子樹和右子樹深度，最終得出結(jié)果。

這種先處理節(jié)點，在處理左子樹，再處理右子樹 的遍歷方式叫做 前序遍歷或者先序遍歷。

時間復(fù)雜度

假設(shè)節(jié)點總數(shù)為n，層數(shù)為x，二叉樹為滿二叉樹。

時間復(fù)雜度計算可以通過 每層的時間復(fù)雜度 * 層數(shù)復(fù)雜度

每層的時間復(fù)雜度：

• 第一層需要遍歷n次，第二層需要遍歷n-1次，第三層需要遍歷n-3次，所以每層的時間復(fù)雜度為O(n)

層數(shù)復(fù)雜度：

• 第一層為1個節(jié)點，第二層為2個節(jié)點，第三層為4個節(jié)點，第x層為2的x-1次方。

借助公式：

n >= 1+2+4+8+...+2^(x-2)+1 
n <= 1+2+4+8+...+2^(L-2)+2^(L-1) 

計算：

n >= 1+2+4+8+...+2^(x-2)+1 
n >= (2^(x-1)-1) + 1  
n >= 2^(x-1) 
x <= log2n+1  

同理：

x >= log2(n+1) 

所以一個接近平衡二叉樹的高度(層數(shù))接近logn。

所以總的時間復(fù)雜度就是 O(nlogn)

空間復(fù)雜度

由于用到了遞歸，用到了堆棧幀，之前說過和最大遞歸深度成正比，所以空間復(fù)雜度為O(n)

解法2

還有沒有更好的解呢?

剛才我們用到的是先序遍歷，但是可以發(fā)現(xiàn)，每個節(jié)點都會計算一遍深度，會有大量重復(fù)計算，所以我們可以試試不重復(fù)的算法?比如直接后序遍歷。

后序遍歷：對于任意節(jié)點來說，先處理左子樹，再處理右子樹，最后再處理節(jié)點本身。

計算深度還是用到剛才的方法：

private int depth(TreeNode root) { 
      if (root == null) return 0; 
      int left = recur(root.left); 
      int right = recur(root.right); 
      return Math.max(left, right) + 1; 
  } 

如果能計算左子樹深度和右子樹深度，那么我們可以直接進行比較，如果發(fā)現(xiàn)某個節(jié)點的左子樹深度和右子樹深度相差大于1，那么就可以直接返回false了。

所以綜合能得出解法二：

class Solution { 
    public boolean isBalanced(TreeNode root) { 
        return recur(root) != -1; 
    } 
 
    private int recur(TreeNode root) { 
        if (root == null) return 0; 
        int left = recur(root.left); 
        if(left == -1) return -1; 
        int right = recur(root.right); 
        if(right == -1) return -1; 
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1; 
    } 
} 

時間復(fù)雜度

n為總節(jié)點，遍歷所有節(jié)點，所以時間復(fù)雜度為O(n)

空間復(fù)雜度

O(n) 

參考

https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/

https://time.geekbang.org/column/article/67856

本文轉(zhuǎn)載自微信公眾號「碼上積木」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系碼上積木公眾號。