日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢(xún)
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷(xiāo)解決方案
LeetCode題解之二叉樹(shù)

前言

今天說(shuō)說(shuō)二叉樹(shù)。

成都創(chuàng)新互聯(lián)公司是一家專(zhuān)注于做網(wǎng)站、網(wǎng)站制作與策劃設(shè)計(jì),肥東網(wǎng)站建設(shè)哪家好?成都創(chuàng)新互聯(lián)公司做網(wǎng)站,專(zhuān)注于網(wǎng)站建設(shè)十余年,網(wǎng)設(shè)計(jì)領(lǐng)域的專(zhuān)業(yè)建站公司;建站業(yè)務(wù)涵蓋:肥東等地區(qū)。肥東做網(wǎng)站價(jià)格咨詢(xún):18980820575

樹(shù)

首先看看什么是樹(shù)??。

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

樹(shù) 是n(n>=0)個(gè)結(jié)點(diǎn)的有限集

其中：

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

二叉樹(shù)

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

比如這種：

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

還有一種二叉樹(shù)叫做 完全二叉樹(shù)。

完全二叉樹(shù): 對(duì)一顆具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)按層編號(hào)，如果編號(hào)為i(1<=i<=n)的結(jié)點(diǎn)與同樣深度的滿二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中位置完全相同，則這棵二叉樹(shù)稱(chēng)為完全二叉樹(shù)。

啥意思呢，比如一個(gè)滿二叉樹(shù)，每個(gè)節(jié)點(diǎn)進(jìn)行順序編號(hào)，如果去了一些節(jié)點(diǎn)，編號(hào)不會(huì)變化，那么就是完全二叉樹(shù)，比如：

這張圖中，綠色樹(shù)是滿二叉樹(shù)，當(dāng)去掉7號(hào)節(jié)點(diǎn)，變成了黃色樹(shù)。

這顆黃色樹(shù)的序號(hào)相對(duì)于滿二叉樹(shù)的序號(hào)都能一一對(duì)應(yīng)，所以這個(gè)黃色樹(shù)就是完全二叉樹(shù)。

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

所以這個(gè)紅色樹(shù)就不是完全二叉樹(shù)，因?yàn)樗鄬?duì)于滿二叉樹(shù)序號(hào)有所改變，已經(jīng)對(duì)應(yīng)不上了。

算法——平衡二叉樹(shù)

說(shuō)了這么多，該來(lái)個(gè)題練練手了。

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

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

  
 
 
 
    
   
  
  
  
  1.   3 
    2. 
   
  
  
  
  2.  / \ 
    3. 
   
  
  
  
  3. 9  20 
    4. 
   
  
  
  
  4.   /  \ 
    5. 
   
  
  
  
  5.  15   7 
    6.

返回 true 。

解析

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

那這個(gè)深度是啥呢?

深度就是根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)經(jīng)過(guò)的邊個(gè)數(shù)

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

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

解法1

首先容易想到的就是把每個(gè)節(jié)點(diǎn)的深度都算出來(lái)，然后進(jìn)行左右節(jié)點(diǎn)比較就能得出是不是平衡二叉樹(shù)。

那么節(jié)點(diǎn)的子樹(shù)深度怎么計(jì)算呢?

遞歸。當(dāng)子節(jié)點(diǎn)為空就返回，否則每次增加一個(gè)單位深度。

  
 
 
 
    
   
  
  
  
  1. /** 
    2. 
   
  
  
  
  2.  * Definition for a binary tree node. 
    3. 
   
  
  
  
  3.  * public class TreeNode { 
    4. 
   
  
  
  
  4.  *     int val; 
    5. 
   
  
  
  
  5.  *     TreeNode left; 
    6. 
   
  
  
  
  6.  *     TreeNode right; 
    7. 
   
  
  
  
  7.  *     TreeNode(int x) { val = x; } 
    8. 
   
  
  
  
  8.  * } 
    9. 
   
  
  
  
  9.  */ 
    10. 
   
  
  
  
  10.  
    11. 
   
  
  
  
  11.     private int depth(TreeNode root) { 
    12. 
   
  
  
  
  12.         if (root == null) return 0; 
    13. 
   
  
  
  
  13.         return Math.max(depth(root.left), depth(root.right)) + 1; 
    14. 
   
  
  
  
  14.     } 
    15.

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

  
 
 
 
    
   
  
  
  
  1. class Solution { 
    2. 
   
  
  
  
  2.     public boolean isBalanced(TreeNode root) { 
    3. 
   
  
  
  
  3.         if (root == null) return true; 
    4. 
   
  
  
  
  4.         return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); 
    5. 
   
  
  
  
  5.     } 
    6. 
   
  
  
  
  6.  
    7. 
   
  
  
  
  7.     private int depth(TreeNode root) { 
    8. 
   
  
  
  
  8.         if (root == null) return 0; 
    9. 
   
  
  
  
  9.         return Math.max(depth(root.left), depth(root.right)) + 1; 
    10. 
   
  
  
  
  10.     } 
    11. 
   
  
  
  
  11. } 
    12.

從根節(jié)點(diǎn)開(kāi)始，計(jì)算每個(gè)左子樹(shù)深度和右子樹(shù)深度的差值，以及下面的每個(gè)節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)深度，最終得出結(jié)果。

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

時(shí)間復(fù)雜度

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

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

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

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

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

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

借助公式：

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

計(jì)算：

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

同理：

  
 
 
 
    
   
  
  
  
  1. x >= log2(n+1) 
    2.

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

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

空間復(fù)雜度

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

解法2

還有沒(méi)有更好的解呢?

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

后序遍歷：對(duì)于任意節(jié)點(diǎn)來(lái)說(shuō)，先處理左子樹(shù)，再處理右子樹(shù)，最后再處理節(jié)點(diǎn)本身。

計(jì)算深度還是用到剛才的方法：

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

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

所以綜合能得出解法二：

  
 
 
 
    
   
  
  
  
  1. class Solution { 
    2. 
   
  
  
  
  2.     public boolean isBalanced(TreeNode root) { 
    3. 
   
  
  
  
  3.         return recur(root) != -1; 
    4. 
   
  
  
  
  4.     } 
    5. 
   
  
  
  
  5.  
    6. 
   
  
  
  
  6.     private int recur(TreeNode root) { 
    7. 
   
  
  
  
  7.         if (root == null) return 0; 
    8. 
   
  
  
  
  8.         int left = recur(root.left); 
    9. 
   
  
  
  
  9.         if(left == -1) return -1; 
    10. 
   
  
  
  
  10.         int right = recur(root.right); 
    11. 
   
  
  
  
  11.         if(right == -1) return -1; 
    12. 
   
  
  
  
  12.         return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1; 
    13. 
   
  
  
  
  13.     } 
    14. 
   
  
  
  
  14. } 
    15.

時(shí)間復(fù)雜度

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

空間復(fù)雜度

  
 
 
 
    
   
  
  
  
  1. O(n) 
    2.

參考

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

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

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


分享題目：LeetCode題解之二叉樹(shù)
本文網(wǎng)址：http://m.5511xx.com/article/codohdg.html