y***m
发帖数: 7027 | 1 这个简单java的，有更简洁明了完善高效结构化的么,thx!
class BinaryTree {
private int data;
private int minNode = Integer.MAX_VALUE;
private BinaryTree leftpoiter;
private BinaryTree rightpoiter;
public BinaryTree() {
}
public BinaryTree(int data) {
this.data = data;
leftpoiter = null;
rightpoiter = null;
}
public void getMinNode(int key) {
getMinNode(this, key);
}
public void getMinNode(BinaryTree root, int key) {
if (root != null) {
i... 阅读全帖 |
|
a******o
发帖数: 106 | 2 高手麻烦检查下代码C#
就像BST inorder 遍历一样， private method 传递 ref k 和 输出的node， 每次遍
历一个数 k-1, 如果k==0 输出当前node 就行。
Kth Min 和 Max 原理完全一样， 只不过把Inorder 的顺序变成 右节点先考虑而已
。
请大侠们批评指正， 谢谢
private static void findKthMinNodeInBST(BinaryTree.Node n, ref int k
, ref BinaryTree.Node outnode)
{
if (n == null) return;
findKthMinNodeInBST(n.Left, ref k, ref outnode);
k--;
if (k < 0) return;
if (k == 0)
{
outnode = n;
... 阅读全帖 |
|
m***g
发帖数: 90 | 3 这个算法里生成的是 bst
12
/\
11 34
/\
22 45
/ \
43 67
/\
56 89
\
98
为啥不是:
12
/\
11 34
\ \
22 45
/ \
43 67
/\
56 89
\
98
bst的生成是先满足右子树么？
public static void main(String args[]) {
BinaryTreeTest b = new BinaryTreeTest();
int data[] = { 12, 11, 34, 45, 67, 89, 56, 43, 22, 98 };
BinaryTreeTest.Bin... 阅读全帖 |
|
h*****i
发帖数: 1017 | 4 #include
#include
using namespace std;
class binaryTree {
public:
int value;
int indx;
binaryTree *left;
binaryTree *right;
binaryTree(){
left = NULL;
right = NULL;
}
};
void insert(binaryTree *bTree, int num, int key){
if(bTree == NULL){
bTree = new binaryTree;
bTree->value = num;
bTree->indx = key;
printf("%d %dn",bTree->value,bTree->indx);
return;
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 5 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-... 阅读全帖 |
|
S**I
发帖数: 15689 | 6 ☆─────────────────────────────────────☆
fengzhongdi (fzd) 于 (Fri May 27 14:30:18 2011, 美东) 提到:
A的onsite,我尽量客观写,大家帮我分析一下
第一个 美国人, 两个string,问第一个是否包含第二个的全部character,扩展是求第一
个string最短的substring包含第二个中所有的character.
我的解法是hashtable, 然后扩展问题是O(n)那个,先找到第一个包含全部的,然后从头
开始删除,接着从尾巴增加那个.面试官表示满意.
OOD是设计card game
交流过程很融洽.
第二个 hiring manage,印度人, 这个人带我去吃饭,然后问了我电梯设计问题,纠缠在
什么时候读楼层,还有如何判断要不要停下来接人.说了快50分钟.我个人感觉还好,反正
他也是都是笑到最后
第三个,白人,一开始问我LRU cache的设计,我直接告诉他double linked list + hash
table,他很吃惊问我是不是准备过,我说是,然后换了一题Bian... 阅读全帖 |
|
f*********i
发帖数: 197 | 7 对树的最长路径,只要DP就可以了啊,就是O(n)复杂度
public static Stack tree_print_longest_depth(BinaryTree root){
if(root==null)
return null;
Stack left = tree_print_longest_depth(root.leftChild);
Stack right = tree_print_longest_depth(root.rightChild);
if(left==null&&right==null){
Stack stack = new Stack ();
stack.push(root);
return stack;
}else if(left==null){
... 阅读全帖 |
|
f*********i
发帖数: 197 | 8 A的onsite,我尽量客观写,大家帮我分析一下
第一个 美国人, 两个string,问第一个是否包含第二个的全部character,扩展是求第一
个string最短的substring包含第二个中所有的character.
我的解法是hashtable, 然后扩展问题是O(n)那个,先找到第一个包含全部的,然后从头
开始删除,接着从尾巴增加那个.面试官表示满意.
OOD是设计card game
交流过程很融洽.
第二个 hiring manage,印度人, 这个人带我去吃饭,然后问了我电梯设计问题,纠缠在
什么时候读楼层,还有如何判断要不要停下来接人.说了快50分钟.我个人感觉还好,反正
他也是都是笑到最后
第三个,白人,一开始问我LRU cache的设计,我直接告诉他double linked list + hash
table,他很吃惊问我是不是准备过,我说是,然后换了一题Bianry tree找两个节点的最
小公共父亲, 一开始是允许有父节点的,然后扩展到没有父亲节点,我给了O(nlogn)解法
public static BinaryTree tree_least_comm... 阅读全帖 |
|
|
d***8
发帖数: 1552 | 9 来自主题: JobHunting版 - 谷歌 电面 BinaryTree* findnextnode(BinaryTree *root, int node_val)
{
stack stk;
BinaryTree *cur = root;
//Find match node
while(cur != NULL)
{
stk.push(cur);
if(cur->value == node_val)
break;
else if (cur->value < node_val)
cur = cur->right;
else if(cur->value > node_val)
cur = cur->left;
}
if (cur == NULL)... 阅读全帖 |
|
t****0
发帖数: 235 | 10 2) it seems not requiring balanced...
http://stackoverflow.com/questions/4235013/create-balanced-bina
search-tree-from-sorted-linked-list
BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
if (start > end) return NULL;
// same as (start+end)/2, avoids overflow
int mid = start + (end - start) / 2;
BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
BinaryTree *parent = new BinaryTree(list->data);
parent->left = leftChild;
list = list->next;
parent->right ... 阅读全帖 |
|
k****i
发帖数: 128 | 11 BinaryTree* randomTreeNode(BinaryTree* root)
{
if(!root) return NULL;
int count=0;
BinaryTree* choice;
randomTreeNode(root, count, choice);
return choice;
}
void preOrder(BinaryTree* root, int& count, BinaryTree*& choice)
{
if(rand()<1/count) {
choice=root;
}
if(root->left) {
count++;
preOrder(root->left, count, choice);
}
if(root->rigth) {
count++;
preOrder(root->right, count, choice);
}
} |
|
i**********e
发帖数: 1145 | 12 这是我的代码，虽然没有那么漂亮简洁，但是比较容易懂。
我可以尝试把代码缩短，但是缩短之后就很难理解了。
void post_order_traversal_iterative(BinaryTree* root) {
bool down = true;
BinaryTree *prev;
stack s;
s.push(root);
while (!s.empty()) {
BinaryTree *curr = s.top();
if (down) {
if (curr->left) {
s.push(curr->left);
} else {
if (curr->right) {
s.push(curr->right);
} else {
down = false;
cout << curr->data << " ";
s.pop();
prev = cu... 阅读全帖 |
|
i**********e
发帖数: 1145 | 13 再试试这个更简洁的思路，去除了使用down的变量。
void post_order_traversal_iterative3(BinaryTree* root) {
stack s;
s.push(root);
BinaryTree *prev = NULL;
while (!s.empty()) {
BinaryTree *curr = s.top();
if (curr->left == prev) {
if (curr->right)
s.push(curr->right);
} else if (!prev || prev->left == curr || prev->right == curr) {
if (curr->left)
s.push(curr->left);
else if (curr->right)
s.push(curr->right);
} else {
cout << curr->data... 阅读全帖 |
|
c***2
发帖数: 838 | 14 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++;
... 阅读全帖 |
|
t*******0
发帖数: 16 | 15 来自主题: JobHunting版 - 谷歌 电面 1. Find the given node, add the track to stack
2. Find next right node
void findnextnode(BinaryTree *root, int node_val)
{
stack s;
int error = 0;
BinaryTree *cur = root;
BinaryTree *cur = NULL;
//Find match node
while(cur!=NULL)
{
s.push(cur);
if(cur->value==node_val)
break;
else if((cur->valueright!=NULL))
{
... 阅读全帖 |
|
a**********3
发帖数: 64 | 16 我怎么觉得不对呢，人家问的是path, 你这个得出的结果是walk.
我觉得最长path就是bt的height
int BinaryTree::height() {
return heightRec(root);
}
int BinaryTree::heightRec(Node *n) {
if (n==0) {
return -1;
} else {
int height_l = heightRec(n->left);
int height_r = heightRec(n->right);
int height_s = height_l;
if (height_r > height_l) {
height_s = height_r;
}
return 1+height_s;
}
}
BinaryTree::BinaryTree() {
root = 0;
}
B
★ 发自iPhone App: Chinese... 阅读全帖 |
|
m*********a
发帖数: 3299 | 17 程序是对的，通不过是因为前面写了一个BST mirror程序，低级错误啊。
想了一天，写了3个版本，最后才想到了这个mirror程序。
下面的三个都是对的
int isBST(binaryTree *node){
return (isBSTUtil2(node,INT_MIN,INT_MAX));
}
int isBSTUtil1(binaryTree *node,int min,int max){
if (node==NULL) return 1;
if (node->keykey>max) return 0;
int ans=1;
ans=ans&&isBSTUtil1(node->left,min,node->key);
ans=ans&&isBSTUtil1(node->right,node->key+1,max);
return ans;
}
int isBSTUtil2(binaryTree *node,int min,int max){
if (node==NULL) return 1... 阅读全帖 |
|
g*********e
发帖数: 14401 | 18 iterative inorder traversal without visited flag
void in_order_traversal_iterative(BinaryTree *root) {
stack s;
BinaryTree *current = root;
while (!s.empty() || current) {
if (current) {
s.push(current);
current = current->left;
} else {
current = s.top();
s.pop();
cout << current->data << " ";
current = current->right;
}
}
} |
|
s******n
发帖数: 20 | 19 这是Leetcode上的一篇文章：
leetcode.com/2010/09/saving-binary-search-tree-to-file.html
里面的重建BST代码我觉得有问题：
void readBSTHelper(int min, int max, int &insertVal,
BinaryTree *&p, ifstream &fin) {
if (insertVal > min && insertVal < max) {
int val = insertVal;
p = new BinaryTree(val);
if (fin >> insertVal) {
readBSTHelper(min, val, insertVal, p->left, fin);
readBSTHelper(val, max, insertVal, p->right, fin);
}
}
}
void readBST(BinaryTree *&root, ifstream &fin) {... 阅读全帖 |
|
s**x
发帖数: 7506 | 20 modifies Caiy's code:
void SiftDown(binaryTree *node)
{
if(!node) return;
binaryTree *largest = node;
if (node->left != NULL && largest->value < node->left->value)
largest = node->left;
if (node->right != NULL && largest->value < node->right->value)
largest = node->right;
if (largest == node) return;
int tmp = node->value;
node->value = largest->value;
largest->value = tmp;
SiftDown(largest);
}
void heapify(binaryTree *node)... 阅读全帖 |
|
s**x
发帖数: 7506 | 21 modifies Caiy's code:
void SiftDown(binaryTree *node)
{
if(!node) return;
binaryTree *largest = node;
if (node->left != NULL && largest->value < node->left->value)
largest = node->left;
if (node->right != NULL && largest->value < node->right->value)
largest = node->right;
if (largest == node) return;
int tmp = node->value;
node->value = largest->value;
largest->value = tmp;
SiftDown(largest);
}
void heapify(binaryTree *node)... 阅读全帖 |
|
l*****a
发帖数: 14598 | 22 刚才面了个contractor
面了道简单的,print binary tree level by level
为节省时间,直接让他去collabedit,我干我的工作
class node{
private int data;
private Node left;
private Node right;
private node parent;
private int level;
public LinkedList listofNode;
public int getData()
{
return this.data;
}
public node getLeftNode()
{
return this.left;
}
public node getRightNode()
{
return this.right;
}
public printTree(Node node )
{
... 阅读全帖 |
|
r*******l
发帖数: 511 | 23 Another solution is to do an in-order traversal of the binary tree, and
verify that the previous value (can be passed into the recursive function as
reference) is less than the current value. This works because when you do
an in-order traversal on a BST, the elements must be strictly in increasing
order. This method also runs in O(N) time and O(1) space.
bool isBSTInOrderHelper(BinaryTree *p, int& prev) {
if (!p) return true;
return (isBSTInOrderHelper(p->left, prev) &&
(p->data > ... 阅读全帖 |
|
s********r
发帖数: 137 | 24 /**
* 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 =... 阅读全帖 |
|
j*******e
发帖数: 1058 | 25 这个超级简单。
就问了2道题目，1道是judge BST。1道是linkedlist loop，多少个node在loop里面。
我写了个recursive的解法，
bool isBSTHelper(BinaryTree *p, int low, int high) {
if (!p) return true;
if (low < p->data && p->data < high)
return isBSTHelper(p->left, low, p->data) &&
isBSTHelper(p->right, p->data, high);
else
return false;
}
bool isBST(BinaryTree *root) {
// INT_MIN and INT_MAX are defined in C++'s library
return isBSTHelper(root, INT_MIN, INT_MAX);
}
java版本的。结果那烙印居然对为什么要传low和high都不知道。问... 阅读全帖 |
|
p**o
发帖数: 3409 | 26 Python的话，对于一个陌生的第三方库，我一般先通读一遍文档，大致定位几个我要用
到的函数和类。实际写代码阶段，在文本编辑器旁边开一个Python/IPython之类的
terminal，把那个库import进来，dir()一下，再次确认我要的那几个函数和类，help(
)一下用法，如果说的太概括看不懂，就拿几个的用例测一下看看是不是我想要的，确
认了再往文本编辑器里正式写。每个函数控制在50行内，每写完一个都做单元测试（可
以用doctest）。反正经常在没有GUI的server端用vim写代码，所以这种写程序方式是
最常用的。
IDE的话，我只有WingIDE的经验，它有两个提示增强的智能提示技巧。一个是assert类
型，比如`assert isinstance(obj, BinaryTree)`，WingIDE会在local scope里假设
obj是BinaryTree类型，并像Java IDE那样给出自动提示。这种assert语句在编译成.
pyo之后被自动忽略，所以不会影响性能。另一种我常用的方法是runtime coding，也
就是直接断点运行到当前函数内部，在ru... 阅读全帖 |
|
m*********a
发帖数: 3299 | 27 int isBST(binaryTree *node){
return (isBSTUtil(node,INT_MIN,INT_MAX));
}
int isBSTUtil(binaryTree *node,int min,int max){
if (node==NULL) return 1;
if (node->key>=min && node->key
isBSTUtil(node->left,min,node->key)&&
isBSTUtil(node->right,node->key+1,max))
return 1;
else return 0;
}
主程序
if (isBST(root)) printf("It is a BST tree.n");
else printf("It is NOT a BST tree.");
然后就是NOT a BST.郁闷 |
|
|
o****p
发帖数: 9785 | 29 大蝌蚪截图上只显示进程了，但是并不代表每个进城里就没有多线程。而且在windows
里的进程即使不是多线程，本质上还是跑的一个独生子线程而已。
你问这种问题真的是让人耻笑了，赶紧收声，讲讲什么linked list或者什么
binarytree啊你兴许还可以插两嘴。 |
|
发帖数: 1 | 30 Write a function isBST(BinaryTree *node) to verify if a given binary tree is
a Binary Search Tree (BST) or not.
限时15分钟，编程语言不限。 |
|
n********u
发帖数: 194 | 31 我刚才写了一下，您看看有没有让code更neat一点的方法？
class BinaryTree{
private static class Node{
int value;
Node left;
Node right;
public Node(int value, Node left, Node right){
this.value=value;
this,left=left;
this.right=right;
}
}
private boolean isMax(Node root, Node lf){
if(root.value < lf.value)
return false;
else{
if ((lf.left == null)&&(lf.right == null))
return true;
else if ((lf.left == null) && (lf.right != null))
|
|
|
|
|
i**********e
发帖数: 1145 | 35 Nice.
This solution is doing Depth-First Traversal (DFS). BFS is fine, but you
need to enqueue all nodes before that level printing a certain level. Here
is a similar solution, but eliminate the currentLevel variable. (we just
start from a level, and decrement the level by one everytime we go into the
next level. When it reaches 1, we have reached the desired level.)
void printLevel(BinaryTree *p, int level) {
if (!p) return;
if (level == 1) {
cout << p->data << " ";
} else {
print... 阅读全帖 |
|
d*******r
发帖数: 208 | 36 for 3.
1) what if tree1 or tree2 is null?
2) Why do you need call tree_least_common_ascenteor 4 times? isn't two times
enough? is if(left!=null&right!=null) ever going to happen?
some simplification of your code:
if(root==null || tree1 == null || tree2 == null)
return null;
if(root.equals(tree1)||root.equals(tree2))
return root;
BinaryTree left = tree_least_common_ascenteor(root.leftChild,tree1,tree2);
if (left != null) {
return left;
} else {
return tree_least_co... 阅读全帖 |
|
w****e
发帖数: 1883 | 37 pseudo code of the top of my head:
public boolean checkTree (BinaryTree bt) {
if (bt.leftchild.key > bt.key || bt.rightchild.key
return false;
else if (bt.leftchild == null && bt.rightchild == null)
return true;
else {
if (bt.leftchild != null )
return checkTree (bt.leftchild)
if (bt.rightchild != null )
return checkTree (bt.rigtchild)
}
}
I am sure the code above can be made cleaner, better, with more elegant
error handling.... 阅读全帖 |
|
|
|
|
|
c**y
发帖数: 172 | 42 Does Post-Order travel work here?
void heapify(binaryTree *node)
{
if (!node) return;
if (node->left)
heapify(node->left);
if (node->right)
heapify(node->right);
int max = node->value;
if (node->left && node->left->value > max) {
max = node->left->value;
}
if (node->right && node->right->value > max) {
max = mode->right->value;
}
if (max == node->value) {
return;
} else if (node->left && max == node->left->value) {
... 阅读全帖 |
|
c**y
发帖数: 172 | 43 Revised solution. Will try to test it if I get a chance today.
void heapify(binaryTree *node)
{
if (!node) return;
if (node->left)
heapify(node->left);
if (node->right)
heapify(node->right);
int max = node->value;
if (node->left && node->left->value > max) {
max = node->left->value;
}
if (node->right && node->right->value > max) {
max = mode->right->value;
}
if (max == node->value) {
return;
} else if (n... 阅读全帖 |
|
c**y
发帖数: 172 | 44 Does Post-Order travel work here?
void heapify(binaryTree *node)
{
if (!node) return;
if (node->left)
heapify(node->left);
if (node->right)
heapify(node->right);
int max = node->value;
if (node->left && node->left->value > max) {
max = node->left->value;
}
if (node->right && node->right->value > max) {
max = mode->right->value;
}
if (max == node->value) {
return;
} else if (node->left && max == node->left->value) {
... 阅读全帖 |
|
c**y
发帖数: 172 | 45 Revised solution. Will try to test it if I get a chance today.
void heapify(binaryTree *node)
{
if (!node) return;
if (node->left)
heapify(node->left);
if (node->right)
heapify(node->right);
int max = node->value;
if (node->left && node->left->value > max) {
max = node->left->value;
}
if (node->right && node->right->value > max) {
max = mode->right->value;
}
if (max == node->value) {
return;
} else if (n... 阅读全帖 |
|
l*****a
发帖数: 14598 | 46 这种题需要新建Node吗？
还是说node.left 相当于 node.previous
node.right相当于node.next |
|
|
|
|
|
