如何使用LeetCode二叉樹

這篇文章主要講解了“如何使用LeetCode二叉樹”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“如何使用LeetCode二叉樹”吧！

創(chuàng)新互聯(lián)公司公司2013年成立，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都網(wǎng)站制作、成都做網(wǎng)站網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元肥西做網(wǎng)站,已為上家服務(wù),為肥西各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:028-86922220

樹

首先看看什么是樹??。

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

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

其中：

• 每個(gè)元素叫做 節(jié)點(diǎn)

• 上一節(jié)是下一節(jié)的 父節(jié)點(diǎn)，比如1是2的父節(jié)點(diǎn)

• 最上面的節(jié)點(diǎn)，也就是沒有父節(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)

• 沒有子節(jié)點(diǎn)的節(jié)點(diǎn)叫做 葉子節(jié)點(diǎn)

二叉樹

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

比如這種：

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

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

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

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

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

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

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

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

算法&mdash;&mdash;平衡二叉樹

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

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

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

  3  / \ 9  20   /  \  15   7

返回 true 。

解析

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

那這個(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       深度 0 ，層數(shù) 1  / \ 2  3      深度 1 ，層數(shù) 2   /  \  4    5   深度 2 ，層數(shù) 3

解法1

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

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

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

/**  * 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;     }

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

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é)點(diǎn)開始，計(jì)算每個(gè)左子樹深度和右子樹深度的差值，以及下面的每個(gè)節(jié)點(diǎn)的左子樹和右子樹深度，最終得出結(jié)果。

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

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

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

時(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次方。

借助公式：

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

計(jì)算：

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)

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

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

空間復(fù)雜度

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

解法2

還有沒有更好的解呢?

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

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

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

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;   }

如果能計(jì)算左子樹深度和右子樹深度，那么我們可以直接進(jìn)行比較，如果發(fā)現(xiàn)某個(gè)節(jié)點(diǎn)的左子樹深度和右子樹深度相差大于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;     } }

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

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

空間復(fù)雜度

O(n)

感謝各位的閱讀，以上就是“如何使用LeetCode二叉樹”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)如何使用LeetCode二叉樹這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！

分享文章：如何使用LeetCode二叉樹
分享路徑：http://muchs.cn/article26/pisgcg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、面包屑導(dǎo)航、網(wǎng)站建設(shè)、服務(wù)器托管、云服務(wù)器、網(wǎng)站營(yíng)銷

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)