i**********e
发帖数: 1145 | 1 How about this top-down approach?
Basically we cannot avoid copying the current path to longest path every
time we update maxDepth, unless we obtain the value of maxDepth by traversing the entire tree beforehand.
void findLongestPath(BinaryTree *p, int &maxDepth, vector &path
, vector &longestPath) {
if (!p) return;
path.push_back(p);
if (!p->left && !p->right && path.size() > maxDepth) {
maxDepth = path.size();
longestPath = path;
}
findLongestPath(p-... 阅读全帖 |
|
f*******t
发帖数: 7549 | 2 这题还好吧，代码很简单：
class TreeNodeStatus {
int maxLength;
int maxDepth;
}
private TreeNodeStatus getTreeNodeStatus(TreeNode node) {
TreeNodeStatus status = new TreeNodeStatus();
if (node == null) {
status.maxLength = 0;
status.maxDepth = 0;
} else if (node.left == null && node.right == null) {
status.maxLength = 1;
status.maxDepth = 1;
} else {
TreeNodeStatus leftStatus = getTreeN... 阅读全帖 |
|
f*******t
发帖数: 7549 | 3 这题还好吧，代码很简单：
class TreeNodeStatus {
int maxLength;
int maxDepth;
}
private TreeNodeStatus getTreeNodeStatus(TreeNode node) {
TreeNodeStatus status = new TreeNodeStatus();
if (node == null) {
status.maxLength = 0;
status.maxDepth = 0;
} else if (node.left == null && node.right == null) {
status.maxLength = 1;
status.maxDepth = 1;
} else {
TreeNodeStatus leftStatus = getTreeN... 阅读全帖 |
|
n****r
发帖数: 120 | 4 public int maxDepth(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null)
return 1;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
public int maxDepth(TreeNode root) {
Stack stack = new Stack();
TreeNode x = root, prev = null;
int maxDepth = 0;
while (x != null || !stack.isEmpty()){
while (x != null){
stack.push(x);
x = x.left;
}
maxDe... 阅读全帖 |
|
c****7
发帖数: 13 | 5 写了个第一题的DFS的非递归解法， 请高手多指教
public static TreeNode findDeepestNode(TreeNode root){
if(root ==null) return root;
int maxDepth = 1;
TreeNode deepestNode = root;
// The previous node we just traversed
TreeNode preNode=null;
// The top item in the stack
TreeNode curNode;
Stack nodeStack = new Stack();
nodeStack.push(root);
// exit until the stack is empty
while(!nodeStack.isEmpty())... 阅读全帖 |
|
h*****g
发帖数: 312 | 6 小弟过几天电面，请教2个问题：
1. 把code 只写成下面这样可以吗？有没有必要写全？比如：没写#include<>...等
例题： implement a function to check if a tree is balanced or not.
int maxDepth(Tree * root) {
if(!root) {
return 0;
}
return 1+max(maxDepth(root->left),maxDepth(root->right));
}
int minDepth(Tree * root) {
if(!root) {
return 0;
}
return 1+min(minDepth(root->left),minDepth(root->right));
}
bool isBalanced(Tree * root) {
return maxDepth(root)-minDepth(root)<=1;
}
########################################### |
|
c***2
发帖数: 838 | 7 There is a solution at
http://www.ihas1337code.com/search/label/binary%20tree
/** See my comments **/
int maxDepthIterative(BinaryTree *root) {
if (!root) return 0;
stack s;
s.push(root);
int depth = 1, maxDepth = 0;
BinaryTree *prev = NULL;
while (!s.empty()) {
BinaryTree *curr = s.top();
if (!prev || prev->left == curr || prev->right == curr) {
if (curr->left) {
depth++;
s.push(curr->left);
} else if (curr->right) {
depth++;
... 阅读全帖 |
|
n**4
发帖数: 719 | 8 just a little practice
1) find the depth of a tree
struct node {
int val;
node * firstChild;
node * nextSibling;
}
int depth(node * tree) {
int maxDepth=0;
node * p;
if (tree==NULL) return 0;
p = tree->firstChild;
while (p) {
maxDepth = max(depth(p),maxDepth);
p=p->nextSibling;
}
return maxDepth;
}
// time complexity: O(N) N the node number of the tree
// space complexity: O(1)
2) check whether a linked list is circular or not.
struct node {
int val;
node * ne... 阅读全帖 |
|
l*********8
发帖数: 4642 | 9 我也写一个，写完才发现和jingoshine的是一样的：）
int BinaryTreeDepth(string & s)
{
int maxDepth(-1), depth(-1);
vector v;
for (int i=0; i
if (s[i] == '(') {
v.push_back(s[i]);
maxDepth = max(maxDepth, ++depth);
} else if (s[i] == '0') {
v.push_back('0');
} else if (s[i] == ')') {
int n=v.size();
if (n<3 || v[n-1]!='0' || v[n-2]!='0' || v[n-3]!='(')
return -1;
v[n-3] = '... 阅读全帖 |
|
r******r
发帖数: 700 | 10 如果计算 deepest node 的整数值，那就是树的高度吧：
“The height of a tree is the length of the path from the root to the
deepest node in the tree. A (rooted) tree with only one node (the root) has
a height of zero.”
这个整值只有一个，就是树的高度。但这个问题的本意好像不是计算树的高度。
但如果要找出具体的 nodes，可能有多个。
看了网上一些相关话题，好像 depth 和 height 的概念有些混淆。比如有计算 最大深
度 的讨论，
public int maxDepth(BSTNode node) {
if (node == null) return 0;
int left = maxDepth(node.left);
int right = maxDepth(node.right);
return 1 + Math.max(left... 阅读全帖 |
|
m******d
发帖数: 75 | 11 不知在这问合时不？
Maximum Depth of Binary Tree
int maxDepth(TreeNode *root) {
if (root == NULL) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) +1;
}
这个accept了， 可是感觉每个depth都多了 1, 比如，只有一个node的tree，理论上
depth应该是0吧，我对depth的概念理解有错吗？ |
|
m******d
发帖数: 75 | 12 【 以下文字转载自 JobHunting 讨论区 】
发信人: mltbbsid (V~), 信区: JobHunting
标 题: leetcode 一题
发信站: BBS 未名空间站 (Tue Jul 8 14:51:01 2014, 美东)
不知在这问合时不？
Maximum Depth of Binary Tree
int maxDepth(TreeNode *root) {
if (root == NULL) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) +1;
}
这个accept了， 可是感觉每个depth都多了 1, 比如，只有一个node的tree，理论上
depth应该是0吧，我对depth的概念理解有错吗？ |
|
b*****e
发帖数: 474 | 13 真的，是DFS, 不过改了一下，用个array存下各层里最近出现的：
void setNextSibling(Node node, int level, Node[] leftNodes) {
if (node == null ) return;
if ( leftNodes[level] != null ) leftNodes[level].nextSibling=node;
leftNodes[level]=node;
foreach (Node n in node.children) {
setNextSibling(n,level+1, leftnodes);
}
}
用的时候，call:
setNextSibling(root,0,new Node[MAXDEPTH]);
(假设MAXDEPTH 已知，或者够大。不然用 ArrayList 也行）。 |
|
Z**********4
发帖数: 528 | 14 因为做leetcode上面isBalancedTree那题想到的。
本来就打算用Crackcode上面的解法去做
bool isBalancedTree(TreeNode* root){
if(!root) return true;
return (getMaxDepth(root) - getMinDepth(root)) < 2;
}
int getMaxDepth(TreeNode* root){
if(!root)return 0;
return std::max(getMaxDepth(root->left), getMaxDepth(root->right)) + 1;
}
int getMinDepth(TreeNode* root){
if(!root)return 0;
return std::min(getMinDepth(root->left), getMinDepth(root->right)) + 1;
}
可是发现有些case通不过。
比如
1
2 ... 阅读全帖 |
|
a**********0
发帖数: 422 | 15 The Unix Commands
其实就是攒了一下网上的资料
# Create a new tar archive.
# the folder dirname/ is compressed into archive_name.tar
tar cvf archive_name.tar dirname/
# Extract from an existing tar archive
tar xvf archive_name.tar
# View an existing tar archive
tar tvf archive_name.tar
# Search for a given string in a file (case in-sensitive search).
grep -i "the" demo_file
# Print the matched line, along with the 3 lines after it.
grep -A 3 -i "example" demo_text
# Search for a given string in all files recur... 阅读全帖 |
|
m*****g
发帖数: 226 | 16 int treeDepthNonRec(treeNode *root)
{
int maxDepth = 0;
if(!root) return 0;
stack > treeNodeStack;
//using traversal
treeNodeStack.push(make_pair(root, root->numChildren));
int depth = 0;
while(!treeNodeStack.empty())
{
pair curNode = treeNodeStack.top();
treeNodeStack.pop();
if(curNode.second)
{
treeNode *curChild = curNode.first->children[curNode.second-1];
|
|
i**9
发帖数: 351 | 17 写了一个
”打印一棵二叉树最深的路径“
大家讨论讨论，这个程序打印所有的longest path,
void longestpath(Node * root,vector &v,int depth){
if(root==NULL){
return;
}
v.push_back(root->data);
if(v.size()==depth){
print(v);
return;
}
vector v2(v);
vector v3(v);
longestpath(root->left,v2,depth);
longestpath(root->right,v3,depth);
}
int main(){
Node * r = buildBST();
int d = maxdepth(r);
vector v;
longestpath(r,v,d);
return 0;
} |
|
c***n
发帖数: 921 | 18 Finding deepest node of tree??
Here is a solution:
- First to find the height of the tree.(do it recursively, O(n) time)
- Then traverses through each node, find the current depth and compare
it with the maxDepth.
- If condition satisfied, print out the item stored in the node.
这是最好方法么？ |
|
c**m
发帖数: 535 | 19 好吧，对于不同的balanced的定义，确实有不同的解法。
但就针对定义1：任意两个叶子节点的高度差不能大于1，方法二也不是正确的
问题在于minDepth()上面
举一个例子，如果一个树是：
N
/ \
N N
/ \
N N
/ \
N N
只有两个叶子，而且高度相同，应该算是balanced
但root的maxdepth/mindepth使用方法二计算出的是4/2，应为左右两个path都是
1/1，2/1，3/1
对于定义2，方法一是正确的。
对于定义1，它比定义2更加严格一些，两个方法都不正确。
另外，LZ是不是看了这个post？
http://stackoverflow.com/questions/742844/how-to-determine-if-b |
|
c****7
发帖数: 13 | 20 各位高手，我想用 Pre-Order Traversal 来实现 maxDepth()。 我用了个hashmap来
保存各个节点的高度.不知道有没有跟优化的解法， 谢谢了！
Here is my code:
public static int maxDepth_preOrderTraversal(TreeNode root){
int maxHight =1;
HashMap nodeHashMap = new HashMap();
if (root==null) return 0;
Stack nodeStack = new Stack();
TreeNode curNode;
nodeStack.push(root);
nodeHashMap.put(root, 1);
while(!nodeStack.isEmpty()){
curNode = nodeStack.pop();
if(curNode.right!=null){
nodeStack.pu... 阅读全帖 |
|
r**h
发帖数: 1288 | 21 class Solution {
public:
int maxDepth(TreeNode *root) {
if(root == NULL) return 0;
stack st;
st.push(root);
TreeNode *prev=NULL, *cur;
int maxHeight = 0;
while(st.size()>0){
cur = st.top();
if(prev==NULL || prev->left==cur || prev->right==cur){
if(cur->left != NULL){
st.push(cur->left);
}
else if(cur->right != NULL){
... 阅读全帖 |
|
X*****1
发帖数: 36 | 22 电面
1， 单例模式 写demo
2， maxDepth of binary tree （lc原题）
3， merge two sorted linkedlist（好像也是原题） |
|
N****w
发帖数: 21578 | 23 想列出所有子目录，不包括 . 开头的，就这样：
find . -maxdepth 1 -type d -name [^.]\*
结果中文目录都列不出来了，
怎么搞？ |
|
N****w
发帖数: 21578 | 24 那个太复杂了
其实如果每个子目录都需要相同的 makefile，俺有一招
SUBDIRS = $(shell find . -maxdepth 1 -o -type d -name [^.]\* -print | sed s/
\\s/\\+/g)
all: makesubdirs target
.PHONY: makesubdirs $(SUBDIRS)
makesubdirs: $(SUBDIRS)
$(SUBDIRS):
if (test ! -f $(subst +,\ ,$@)/Makefile); then cp Makefile $(subst +
,\ ,$@); fi
$(MAKE) -C $(subst +,\ ,$@)
target:
do sth |
|
