d******i
发帖数: 76 | 1 谢谢@wwwyhx大牛贡献的题。看了帖子里面的回复后，有了些思路，虽然对于牛人们，
这道题很简单，对于还是菜鸟的我还是很难的，发个帖子，供大家讨论，希望最
终得出正确的答案吧。
“我面的时候有一简单题一定要O(n), 找树的unival个数(就是这个节点开始所有子树都
一样的节点数) ”
题的意思是，找到这样的子树，满足子树中所有节点的值相等。计算满足此条件的子树
中节点的总个数。（希望没有理解错。）
例子1：
1
结果为 1
例子2：
1
1 1
结果为 3
例子3：
1
2 3
结果为2（2, 3）
例子4：
1
2 3
2
结果为：3 ({2,2}, {3})
例子 5：
1
2 3
2
4
结果为： 2 （4，3）；
下面是C++代码，大家指正
---------------更新：不需要看我写的了，直接看楼下的解法吧，哈哈。-----------
----
#include
#include
using namespace std;
struct TreeN... 阅读全帖 |
|
d******i
发帖数: 76 | 2
答案是1
From wiki: "A subtree of a tree T is a tree consisting of a node in T and
all of its descendants in T, ... each node is the root node of the subtree
it determines"
叶子节点自身也可为一个subtree，只不过没有descendants。
所以 节点 3 是unival substree |
|
g****n
发帖数: 431 | 3 subtree只有一个定义。你刚才那个例子并不是subtree。 |
|
w**z
发帖数: 8232 | 4 我给个题吧。最近面试碰到的
Find number of subtrees in a tree which all nodes have the same value.
public int FindNumberOfSubTreesWithSameValue(Node root)
Note:
The leaf node itself is a subtree.
5
1 2
1 3
1
answer is 4 |
|
c**y
发帖数: 172 | 5 问题简单概述：Binary Tree T1（大）和T2（小），判断T2是不是T1的substree。
CC150给的解法是对于每一个Tree，用InOrder和PreOrder的方法生成两个序列，然后判
断T2的两个序列是不是T1两个序列的substring。CC150还有brutal force的解法（这里
就不讨论了）。
我的问题是
1.这个序列比较的解法要求T1和T2不能有duplicate元素？这个应该是确定的，参见
http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-
2.为什么不比较PostOrder生成的序列呢？下面是一个反例（如果只用PreOrder和
InOrder
，返回True，但是实际应该是False）
T1:
1
/ \
2 3
\
4
T2:
1
/ \
2 3
T1:
InOrder: 2134
PreOrder: 1234
T2:
InOrder: 213
PreOrder: 123
如果只用InOrder和... 阅读全帖 |
|
c**y
发帖数: 172 | 6 特殊字符就是()
以下是个inorder的例子
printf("(");
inrodervisit(p_node->p_leftchild);
printf(")");
printf(p_node->value);
printf("(");
inrodervisit(p_node->p_rightchild);
printf(")");
这样每次访问一个新的subtree，总是会打印一个（）surrounding这个subtree的序列
。 |
|
Z*****Z
发帖数: 723 | 7 it's fine. just realized there are different ways to interprete 'subtree' |
|
H***e
发帖数: 476 | 8 bottom up,
each subtree传true/false 给parent ,如果都为true
则比较left/right值是不是跟自己一样， 然后都相同就传true上去。 (同时update
number总数). |
|
p*****2
发帖数: 21240 | 9 如果左右subtree都是的话，并且左右和root相等的话加1就可以了吧？ |
|
g*****e
发帖数: 282 | 10 也凑个热闹，假设tree nodes的值都是正整数。如果subtree是null认为root（即null
）值是0，非unival sub tree的node是-1.
int count=0;
getUnivalNode(root);
int getUnivalNode(node root)
{
if (root == null)
{
return 0;
}
int left = getUnivalNode(root.left);
int right = getUnivalNode(root.right);
if ((left == 0 || left == root.val)
&& (right == 0 || right == root.val))
{
count++;
return root.val;
}
return -1;
... 阅读全帖 |
|
r*****e
发帖数: 146 | 11 largest balanced subtree of a binary tree。
写一下，怎么也没对。。。大家讨论一下？ |
|
B********t
发帖数: 147 | 12 是你自己弄错了吧。。
用preorder inorder的方法，T2就不是T1的subtree. preorder inorder的这种方法是
需要在node之间加一些special character的，以便知道哪些左 右子树为NULL.
T1：inorder: 0201034
T2: inorder: 0201030 |
|
|
T******7
发帖数: 1419 | 14 2. 查找binary tree中有多少个uni－valued subtree，uni－valued tree的定义是所
有其中node value值一样。
这题有什么好思路么？求一点指点 謝謝 |
|
N******n
发帖数: 3003 | 15 A binary tree, consider this one
随机的从node list里面选出来两个，找到包含他们两个最小的subtree? 如果知道他们
彼此的距离：
下面是1：20个node的彼此之间打距离，最小距离的两个node连起来。 编码21-38的
node,是新生成的node编号。
1 18 0.173245245659265
13 14 0.198593606247982
9 22 0.204966317390519
3 17 0.208193563194276
19 20 0.221074833179044
7 16 0.223642554659747
4 10 0.238063832905942
6 23 0.310995388212581
11 26 0.324846848580523
5 12 0.330318775959661
8 27 0.382607731542580
15 24 0.418953465919111
21 25 0.463726157024167
2 31 0.556103951657053
30 32 0.8011350664129... 阅读全帖 |
|
o*******w
发帖数: 349 | 16 "On the Subtree Size Profile of Binary Search trees"
Florian Dennert, Rudolf GrÜbel
July 2010 Combinatorics, Probability and Computing , Volume 19 Issue 4
请发到
M*************[email protected]
深表感谢！ |
|
s*********3
发帖数: 389 | 17 It seems that it doesn't need to use recursive. Traverse the BST, if the
root value is less than target value, find the minimum value of the right
subtree and compare the difference between the root value and the target value vs. the minimum value of the right subtree and the target value. Similar for left subtree.
//Given a BST, find the number closest to a target number
public Float searchClosestNumber(TreeNode x, float d) {
if (x == null) {
return null;
}
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 18 Please don't get confuse :)
I don't know what you mean by min leaf node and max leaf node. Is it the
node that has min and max values? If it is, then your definition of balanced
bst is wrong.
The correct definition for a balanced bst is:
A tree whose subtrees differ in height by no more than one and the subtrees
are height-balanced, too.
When you subdivide the array and construct the bst top-down, you are
essentially maintaining the following invariant in each subdivision:
|#nodes in left subtre... 阅读全帖 |
|
s****n
发帖数: 48 | 19 我写了个练手的,可以处理non-full binary tree。几个要点：
1.把parent node传给recursive function
2.每次recursive call只负责连接当前root。因为parent node作为参数传进来了，我
可以access parent's next link。并且这个时候所有上层的next links都已经连接好
了。
3.左右子树分别递归处理。先处理右子树，再处理左子树。
public void AddNextLink(Tree tree)
{
if (tree.Root == null)
{
return;
}
tree.Root.Next = null;
this.AddNextLink(tree.RightTree, tree, false);
this.AddNextLink(tree.LeftTree, tree, t... 阅读全帖 |
|
S*******C
发帖数: 822 | 20 import java.util.Stack;
/*
* Given Tree and Node n and int k, print all node which are at physical
distance <=k from n
* @Amazon intern
*/
public class Solution {
public static void main(String args[]){
Solution solution = new Solution();
TreeNode a = new TreeNode(8);
TreeNode b = new TreeNode(6);
TreeNode c = new TreeNode(10);
TreeNode d = new TreeNode(9);
TreeNode e = new TreeNode(12);
TreeNode f = new TreeNode(4);
TreeNode ... 阅读全帖 |
|
d****2
发帖数: 6250 | 21 preorder: 1 2 3 4 5
inorder: 3 2 4 1 5
root 1
left subtree preorder 2 3 4
left subtree inorder 3 2 4
right subtree preorder 5
right subtree inorder 5
recursively work on left subtree and right subtree with the known
preorder and inorder lists. |
|
S**I
发帖数: 15689 | 22 ☆─────────────────────────────────────☆
sugarbear (sugarbear) 于 (Thu Apr 7 00:42:48 2011, 美东) 提到:
找 二叉树 两个最大的相同子树
没答上来。
见了四个，被拒了。 第二个是manager，后来主动写信跟我联系，说把我推荐给industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更难吧？ 求祝福！
☆─────────────────────────────────────☆
boohockey (Pursuit of Dreams!) 于 (Thu Apr 7 10:27:03 2011, 美东) 提到:
bless
这道题有没有正解
industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更
难吧？ 求祝福！
☆─────────────────────────────────────☆
grass (美丽人生) 于 (Thu Apr... 阅读全帖 |
|
I*******l
发帖数: 203 | 23 Update: fix some boundary condition checks
recursively call a function Node* cc(Node* root) to find out where to insert an extra node, where cc checks left subtree first and then right subtree to find a non-full subtree. It returns NULL if both subtrees are full.
Node* cc(Node* root)
{ // make sure that leaf node return NULL
if (root == NULL)
return NULL;
// first check if root has both children, if not return root
if (root->left != NULL && root->right == NULL)
return root;... 阅读全帖 |
|
s**********e
发帖数: 326 | 24 Given two BTs T1 and T2, return the larest common subtree
idea:
step one:
首先分别对T1, T2做预处理，求出每个subtree的nodes总个数，把得到的结果存到
hashtable里面，这一步时间复杂度O(N), N=number of nodes
step two:
从root开始从上到下对每对相对应的node pair，判断以他们为root的subtree是否相同
given node1 from t1, node2 from t2
f(node1,node2)= true if node1 == node2 && f(node1.left, node2.left) && f(
node1.right, node2.right)
这个过程可以使用dp的思想，建个hashtable存放f的值，key=node1.hashcode+"-"+
node2.hashcode， value=boolean
这一步时间复杂度O(N)
step three:
有了第一步的每个subtree 的size, 第二步的每对s... 阅读全帖 |
|
d**********o
发帖数: 1321 | 25 第二次作业report
#+latex_class: cn-article
#+latex_header: \usepackage{CJKutf8}
#+latex_header: \begin{CJK}{UTF8}{gbsn}
#+latex_header: \lstset{language=c++,numbers=left,numberstyle=\tiny,
basicstyle=\ttfamily\small,tabsize=4,frame=none,escapeinside=``,
extendedchars=false,keywordstyle=\color{blue!70},commentstyle=\color{red!55!
green!55!blue!55!},rulesepcolor=\color{red!20!green!20!blue!20!}}
#+title: CS572 Project 2 Report
#+author: (me~~~)
#+begin_abstract
|---------------------------+------------... 阅读全帖 |
|
d**********o
发帖数: 1321 | 26 第二次作业report
#+latex_class: cn-article
#+latex_header: \usepackage{CJKutf8}
#+latex_header: \begin{CJK}{UTF8}{gbsn}
#+latex_header: \lstset{language=c++,numbers=left,numberstyle=\tiny,
basicstyle=\ttfamily\small,tabsize=4,frame=none,escapeinside=``,
extendedchars=false,keywordstyle=\color{blue!70},commentstyle=\color{red!55!
green!55!blue!55!},rulesepcolor=\color{red!20!green!20!blue!20!}}
#+title: CS572 Project 2 Report
#+author: (me~~~)
#+begin_abstract
|---------------------------+------------... 阅读全帖 |
|
m*****k
发帖数: 64 | 27 你是说，如果知道at each node that records the number of nodes in the subtree
rooted at it. 那么，可以根据number of nodes in left and right subtrees,来找?
比如说left subtree has 3 nodes, right subtree has 3nodes, and we want to
find the 6th biggest node, then it should be on left subtree,then
recursively find it? so it is o( lgn). Is it what you are talking about?
information
it? |
|
c*******w
发帖数: 63 | 28 仅仅靠Index(Parent)
子树的根啊?
比如:
int inorderSeq[]= {2,4,9,8,3,1,6,7,5};
int levorderSeq[]={1,2,5,3,6,4,7,8,9};
When you go to the first element of level order 1, it is the root, 1
separate the in order seq into two parts. The left part is its left subtree
[2,4,9,8,3], the right part is its right subtree[6,7,5]. The program goes to
the left subtree, we need find which one is the root of left subtree.
The root of left subtree is the one with the minimum level |
|
i****c
发帖数: 102 | 29 M公司的，上次懒，没整理完就没发
1）
Given two trees, a node in one tree matches a node in the other tree if
their paths (from root) contain the same
labels in the same order.
1) given two trees, find all matched nodes.
2) given two trees, find the largest matched subtrees (each node in one
subtree has a matched node in the other
subtree, and the order of the sibling nodes in two subtrees is the same)
example:
tree 1)
A is root, has children from left to right (B C D E)
tree 2)
A is root, has children from left ... 阅读全帖 |
|
l***i
发帖数: 1309 | 30 struct Node {
Node *left, *right;
int val;
};
// returns true if subtree at root is BST
// the pair is minval and maxval of this subtree
typedef pair pii;
pair isBST(Node *root)
{
if (root == NULL) return make_pair(true, pii(0,0));
if (root->left == NULL && root->right == NULL)
return make_pair(true, pii(root->val, root->val));
pair p1, p2;
bool b1, b2, ans;
int s1, s2, t1, t2, vmin, vmax;
p1 = isBST(root->left);
p2 = isBST(root->righ... 阅读全帖 |
|
a***e
发帖数: 413 | 31 Given n, generate all structurally unique BST's (binary search trees) that
store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
1 3 3 2 1
/ / /
3 2 1 1 3 2
/ /
2 1 2 3
这种题如果没见过我很难想出来，看了答案也不知道复杂度怎么算。汗， 现在在国内
还惦记着这些题。
class Solution {
public:
vector generateTrees(int n) {
if (n==0) retur... 阅读全帖 |
|
b******g
发帖数: 3616 | 32 定义是对的。但是left/right subtree和每个node的two subtree是一回事。left/
right subtree并不特指是root的。而定义中的two subtree也必须属于同一个node下。
我举的那个反例里你能找出哪个node下的two subtree高度差1以上吗？
depth |
|
i**********e
发帖数: 1145 | 33 更新，一道新面试题总结：
Largest BST in a Binary Tree
要求在树里找最大的 BST subtree。注意，这里指的是 subtree，如果不清楚定义，先
跟面试官确定一下。subtree 在维基百科的定义是指包括树节点和它所有的
descendents。做这题前必须知道怎么才能判断树是不是 BST。这题的巧妙之处在于利
用了 bottom-up 的 Depth-first 遍历来解决所有 top-down 遍历的难处。当然，如果
面试官要求的是 largest BST（不一定是 subtree），那就是另外一套思路了。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 34 这题没那么容易。
我想了想，似乎很难用 bottom dfs 来解。
top down dfs 肯定可以，但是效率没那么好（有很多重复的扫描）
还有，有一个要弄清楚的是 subtree 的定义。。。
根据 wikipedia 里 subtree 的定义，
A subtree of a tree T is a tree consisting of a node in T and all of its
descendants in T.
不知道你想的 subtree 是一个 tree 里面任何一小部分，或是所有子节点都必须吻合
才行？
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
n**4
发帖数: 719 | 35 2楼进化树能展开说一下吗？
我有一个解法 记得是版上某大牛做的
basic idea: use a hash function to get a digest of a tree by hashing its
child subtrees' digests:
digest(tree)=0 if tree is empty
digest(tree)=hash(digest(LeftChildTree),digest(RightChildTree),rootVal)
therefore, this problem can be solved by a post-order traversal. On the
traversal, all the subtrees are digested and registered. If a match occurs,
the roots of both trees and their size are compared and recorded.
the hashTable_get/put functions need the tree digest... 阅读全帖 |
|
F********u
发帖数: 7 | 36 bool is_same_BST(int *A, int m, int a_min, int a_max, int *B, int n, int b_
min, int b_max)
{
if( A == NULL || B == NULL )
return false;
if( m == 0 && n == 0 )
return true;
if( m == 0 || n == 0 )
return false;
if( A[0] != B[0] )
return false;
int i, j, a, b;
// A tree -> left subtree root
for( i = 1; i < m; i++ )
{
if( A[i] > a_min && A[i] < A[0] )
break;
}
// B tree -> left subtree root
for( j = 1; j... 阅读全帖 |
|
s********r
发帖数: 137 | 37 /**
* Took FightingXu's algorithm and implemented in JAVA:
*/
public static boolean isSameBST(int[] arrA, int aOffset, int aMin, int aMax,
int[] arrB, int bOffset, int bMin, int bMax)
{
if (arrA == null || arrB == null)
return false;
if (aOffset > -1 && aOffset == 0 && bOffset > -1 && bOffset == 0)
return true;
if (arrA.length == aOffset || arrB.length == bOffset)
return false;
if (aOffset > -1 && bOffset > -1 && arrA[aOffset] != arrB[bOffset])
return false;
int i, aLeftOffset = 0, bLeftOffset =... 阅读全帖 |
|
t**********h
发帖数: 2273 | 38 有nullpointer的异常。每次调用的时候检查一下，或者第一行先判断root是否为空
很不错的想法。如果已经是完全树，则跑到最左下角节点去insert
insert an extra node, where cc checks left subtree first and then right
subtree to find a non-full subtree. It returns NULL if both subtrees are
full. |
|
D********g
发帖数: 650 | 39 不错的想法，不过这个算法只能handle下面这种case:
1
2 4
3
但是cc对下面的case会return NULL,但是我们希望cc return 4.
1
2 4
3 5
insert an extra node, where cc checks left subtree first and then right
subtree to find a non-full subtree. It returns NULL if both subtrees are
full. |
|
C***U
发帖数: 2406 | 40 他是bst树
所以给定来的顺序以后树bst就确定了
可以用递归算法来做这个问题吧
N(k)=2(N(x)+N(y))
这里x是left subtree的node数
y是right subtree的node数
x+y=k-1
这里的2倍是因为left subtree和right subtree的进来顺序可以整体交换一下
不知道这个样对不对 |
|
f*********d
发帖数: 140 | 41 //我上个代码吧, 没有测试过, 有错误或者bug请指出。。。
//这里假设所有节点的值都不一样, 如果存在一样的节点值, 需要一点修改。。。
struct BSTNode {
BSTNode* left;
BSTNode* right;
int val;
}
//print open interval (min_val, max_val) in r
void PrintBST(BSTNode* r, int min_val, int max_val)
{
if(r == NULL) return;
if(r->val <= min_val) PrintBST(r->right, min_val, max_val);
else if(r->val >= max_val) PrintBST(r->left, min_val, max_val);
else {
PrintBST(r->left, min_val, r->val);
cout << r->vale;
PrintBST(r-... 阅读全帖 |
|
e***s
发帖数: 799 | 42 刚写的，思想是，node的总数等于left subtree + right subtree + 1；
如果left subtree perfect 直接算 2^h -1; 如果不，递归进去
同理right subtree
public static int nodesInCompleteBT(TreeNode root){
if(root == null)
return 0;
if(root.left == null) // one node tree
return 1;
int height = 1;
TreeNode node = root.left;
while(node != null)
{
node = node.left;
height++;
}
return nodesInCompleteBTHelper(root, height);
}
... 阅读全帖 |
|
M*****D
发帖数: 22 | 43 谢谢解答！
还是对楼主您unary tree第二问找出5个有所疑问
第一个问题是，楼主您给出的b和c两个1的subtree，应该是一样的，这样就不能算
distinct了
第二个问题是，楼主您给出的e这个subtree，是以root开始的subtree，那应该就是这
个tree本身了，怎么能砍掉左半部分呢？
抱歉，我尝试按您的树
1
/
1 1
/ /
2 1 1
去找unary distinct subtree, 我能找到
2
1
1
/
1 1
就这3个。。 |
|
I*********y
发帖数: 185 | 44 书上说的recursive方法是每一步判定
1）左边subtree是否balanced
2）右边subtree是否balanced
3）左边的subtree height与右边subtree height是否最多相差1
我想问一下如果这样做有什么问题：
1）recursively求出整个tree的maximum height O(n)
2) recursively求出整个tree的minimum height O(n)
3) 检查两个高度是否最多差1
我是算法弱人，求大牛指点。 |
|
F*****o
发帖数: 32 | 45 I do not think this is a balanced BT. see definition:
A height-balanced binary tree is defined as a binary tree in which the depth
of the two subtrees of every node never differ by more than 1.
It is"two subtrees", not "left subtree and right subtree".
You can use min and max method |
|
s*******r
发帖数: 9 | 46 250 Count Univalue Subtrees
Given a binary tree, count the number of uni-value subtrees.
A Uni-value subtree means all nodes of the subtree have the same value.
For example:
Given binary tree,
5
/ \
1 5
/ \ \
5 5 5
return 4.
195 / 197 test cases passed.
有一个case通不过
Input:
[5,5,5,5,5,null,5]
Output:
4
Expected:
6
实在没看出来有6个，是我题目理解不对？ |
|
w****g
发帖数: 44 | 47 3. We define a simple unbalanced binary search tree of integers as
follows:
- Each node in the tree contains an integer, and possibly pointers to
a left subtree and/or a right subtree
- Each node in the left subtree contains an integer that is smaller
than the integer in this node
- Each node in the right subtree contains an integer that is larger
than the integer in this node
- The tree either has a root node or it is empty
To insert a number into the tree, we start a |
|
b***k
发帖数: 2673 | 48 ☆─────────────────────────────────────☆
wealdg (wwwnet) 于 (Wed Aug 6 18:05:11 2008) 提到:
3. We define a simple unbalanced binary search tree of integers as
follows:
- Each node in the tree contains an integer, and possibly pointers to
a left subtree and/or a right subtree
- Each node in the left subtree contains an integer that is smaller
than the integer in this node
- Each node in the right subtree contains an integer that is larger
than the integer in this node
- |
|
c**y
发帖数: 172 | 49 问题是找到一个binary tree中所有路径，对于每一条这样得路径，其成员节点的和等
于一个指定的值。附带的说明是符合条件的路径不是必须从root开始。下面是
CareerCup的问题说明和解答。
我的疑惑是这个solution给出的路径（们）确实可以不是从root开始，但是每一条路径
一定是沿着root到某一个叶子节点（即在较低level的端点一定是在一个以在较高level
端点为顶点的subtree里面），而不会出现路径的两端出现在两个不同的subtree中。
However，题的说明之中并没有指明路径的两端不可以出现在两个不同的subtree中。
如何修改下面的solution使得上面所说的路径可以被找到呢？Thanks
Problem:
You are given a binary tree in which each node contains a value. Design an
algorithm to print all paths which sum up to that value. Note that it can be
any path in the tree |
|
l*****a
发帖数: 14598 | 50 Binary search tree
From Wikipedia, the free encyclopedia
In computer science, a binary search tree (BST) or ordered binary tree
is a node-based binary tree data structure which has the following
properties:
The left subtree of a node contains only nodes with keys less than the
node's key.
The right subtree of a node contains only nodes with keys greater than
the node's key.
Both the left and right subtrees must also be binary search trees. |
|
