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 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.
Example:
Input: 1 / 2 3 / / 4 5 6 Output: 6Solution
class Solution { public int countNodes(TreeNode root) { if (root == null) return 0; int height = 0; TreeNode left = root.left, right = root.right; while (left != null && right != null) { height++; left = left.left; right = right.right; } if (left == null && right == null) return (1 << (height+1)) - 1; else return 1 + countNodes(root.left) + countNodes(root.right); } }
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/72536.html
摘要:題目要求計(jì)算一個(gè)完全二叉樹的節(jié)點(diǎn)個(gè)數(shù)。其中完全二叉樹是指除了最后一行,其余的每一行都必須是滿節(jié)點(diǎn)的樹。當(dāng)然超時(shí)啦思路二講道理的遞歸思路一很明顯沒(méi)有充分利用這是一顆完全二叉樹的條件。 題目要求 Given a complete binary tree, count the number of nodes. Definition of a complete binary tree fro...
摘要:題目解答學(xué)了的方法哈哈這里是從開始算起,所以求出來(lái)的結(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è)滿足,就返回每次訪問(wèn)一個(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...
閱讀 2222·2021-11-18 10:02
閱讀 3480·2021-11-15 11:36
閱讀 1116·2019-08-30 14:03
閱讀 725·2019-08-30 11:08
閱讀 2761·2019-08-29 13:20
閱讀 3287·2019-08-29 12:34
閱讀 1375·2019-08-28 18:30
閱讀 1642·2019-08-26 13:34