資訊專欄INFORMATION COLUMN
摘要：題目解答學(xué)了的方法哈哈這里是從開(kāi)始算起，所以求出來(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 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.
解答：
public class Solution {
//學(xué)了enum的方法哈哈
public enum Direction {
LEFT, RIGHT
}
public int getDepth(TreeNode root, Direction dir) {
int depth = 0;
//這里是從root開(kāi)始算起，所以求出來(lái)的結(jié)果是實(shí)際depth + 1
while (root != null) {
depth++;
if (dir == Direction.LEFT) {
root = root.left;
} else {
root = root.right;
}
}
return depth;
}
public int countNodes(TreeNode root) {
if (root == null) return 0;
int leftDepth = getDepth(root, Direction.LEFT);
int rightDepth = getDepth(root, Direction.RIGHT);
if (leftDepth == rightDepth) {
//1 << leftDepth是2^(leftDepth)
return (1 << leftDepth) - 1;
} else {
//這一步很巧妙，把根結(jié)點(diǎn)加上，然后分治左結(jié)點(diǎn)和右結(jié)點(diǎn)，如果是葉子結(jié)點(diǎn)，在countNodes中就返回1
return 1 + countNodes(root.left) + countNodes(root.right);
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64885.html
摘要：題目要求計(jì)算一個(gè)完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)。其中完全二叉樹(shù)是指除了最后一行，其余的每一行都必須是滿節(jié)點(diǎn)的樹(shù)。當(dāng)然超時(shí)啦思路二講道理的遞歸思路一很明顯沒(méi)有充分利用這是一顆完全二叉樹(shù)的條件。 題目要求 Given a complete binary tree, count the number of nodes. Definition of a complete binary tree fro...
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...
摘要：如果不等于，則是左子樹(shù)的節(jié)點(diǎn)數(shù)，加上右子樹(shù)的節(jié)點(diǎn)數(shù)，加上自身這一個(gè)。注意這里在左節(jié)點(diǎn)遞歸時(shí)代入了上次計(jì)算的左子樹(shù)最左深度減，右節(jié)點(diǎn)遞歸的時(shí)候代入了上次計(jì)算的右子樹(shù)最右深度減，可以避免重復(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...
摘要： 112. Path Sum Problem Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node...
閱讀 2347·2021-11-15 11:38
閱讀 3557·2021-09-22 15:16
閱讀 1200·2021-09-10 11:11
閱讀 3170·2021-09-10 10:51
閱讀 2950·2019-08-30 15:56
閱讀 2789·2019-08-30 15:44
閱讀 3194·2019-08-28 18:28
閱讀 3533·2019-08-26 13:36
