資訊專欄INFORMATION COLUMN
摘要：題目要求計(jì)算一個(gè)完全二叉樹的節(jié)點(diǎn)個(gè)數(shù)。其中完全二叉樹是指除了最后一行，其余的每一行都必須是滿節(jié)點(diǎn)的樹。當(dāng)然超時(shí)啦思路二講道理的遞歸思路一很明顯沒有充分利用這是一顆完全二叉樹的條件。
題目要求
Given a complete binary tree, count the number of nodes. Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
計(jì)算一個(gè)完全二叉樹的節(jié)點(diǎn)個(gè)數(shù)。其中完全二叉樹是指除了最后一行，其余的每一行都必須是滿節(jié)點(diǎn)的樹。
思路一 ：不講道理的遞歸直接返回左子樹和右子樹的葉結(jié)點(diǎn)的個(gè)數(shù)。當(dāng)然超時(shí)啦
public int countNodes(TreeNode root) {
if(root==null) return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
思路二：講道理的遞歸
思路一很明顯沒有充分利用這是一顆完全二叉樹的條件。從另一個(gè)角度看，一顆完全二叉樹的左子樹和右子樹有兩種情況
左子樹比右子樹高
左子樹和右子樹一樣高
當(dāng)左子樹和右子樹一樣高時(shí)，說明左子樹本身是一顆滿二叉樹，它的元素個(gè)數(shù)為2^h左-1。
當(dāng)左子樹比右子樹高時(shí)，說明右子樹本身是一顆滿二叉樹，它的元素個(gè)數(shù)為2^h右-1(h為樹的高度)
所以每一次通過判斷左右子樹的高度可以得到其中一棵子樹的元素個(gè)數(shù)，這時(shí)再遞歸到另一顆子樹繼續(xù)計(jì)算直到當(dāng)前元素為null。
代碼如下：
int height(TreeNode root) {
return root == null ? -1 : 1 + height(root.left);
}
public int countNodes2(TreeNode root) {
int h = height(root);
return h < 0 ? 0 :
height(root.right) == h-1 ? (1 << h) + countNodes2(root.right)
: (1 << h-1) + countNodes2(root.left);
}
思路三：遞什么歸！
當(dāng)遞歸轉(zhuǎn)化為循環(huán)且該循環(huán)并不需要使用棧這種數(shù)據(jù)結(jié)構(gòu)時(shí)，性能往往會(huì)得到質(zhì)的飛躍。在上面的思路二中采用遞歸，在這里我們將遞歸轉(zhuǎn)變?yōu)檠h(huán)。同時(shí)我們只需要計(jì)算一次樹的高度，因?yàn)槊恳淮芜x擇的子樹的高度都是上一個(gè)高度-1。
int height2(TreeNode root){
if(root==null) return -1;
int height = 0;
while(root.left!=null) {height++; root=root.left;}
return height;
}
public int countNodes3(TreeNode root) {
int count = 0;
int height = height2(root);
while(root!=null){
if(height2(root.right)==height-1){
count += 1<
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/71145.html
Problem Given a complete binary tree, count the number of nodes. Note: Definition of a complete binary tree from Wikipedia:In a complete binary tree every level, except possibly the last, is completel...
摘要：題目解答學(xué)了的方法哈哈這里是從開始算起，所以求出來的結(jié)果是實(shí)際是這一步很巧妙，把根結(jié)點(diǎn)加上，然后分治左結(jié)點(diǎn)和右結(jié)點(diǎn)，如果是葉子結(jié)點(diǎn)，在中就返回 題目：Given a complete binary tree, count the number of nodes. Definition of a complete binary tree from Wikipedia:In a compl...
摘要：如果不等于，則是左子樹的節(jié)點(diǎn)數(shù)，加上右子樹的節(jié)點(diǎn)數(shù)，加上自身這一個(gè)。注意這里在左節(jié)點(diǎn)遞歸時(shí)代入了上次計(jì)算的左子樹最左深度減，右節(jié)點(diǎn)遞歸的時(shí)候代入了上次計(jì)算的右子樹最右深度減，可以避免重復(fù)計(jì)算這些深度做的冪時(shí)不要用，這樣會(huì)超時(shí)。 Count Complete Tree Nodes Given a complete binary tree, count the number of nod...
Problem Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST. Assume a BST is defined as follows: The left subtree of a node c...
摘要：解題思路利用遞歸，對(duì)于每個(gè)根節(jié)點(diǎn)，只要左子樹和右子樹中有一個(gè)滿足，就返回每次訪問一個(gè)節(jié)點(diǎn)，就將該節(jié)點(diǎn)的作為新的進(jìn)行下一層的判斷。代碼解題思路本題的不同點(diǎn)是可以不從開始，不到結(jié)束。代碼當(dāng)前節(jié)點(diǎn)開始當(dāng)前節(jié)點(diǎn)左節(jié)點(diǎn)開始當(dāng)前節(jié)點(diǎn)右節(jié)點(diǎn)開始 Path SumGiven a binary tree and a sum, determine if the tree has a root-to-lea...
閱讀 880·2021-11-25 09:43
閱讀 3708·2021-11-19 09:40
閱讀 919·2021-09-29 09:34
閱讀 1840·2021-09-26 10:21
閱讀 906·2021-09-22 15:24
閱讀 4242·2021-09-22 15:08
閱讀 3302·2021-09-07 09:58
閱讀 2754·2019-08-30 15:55
