d******y
发帖数: 244 | 1 头一个指针从左到右找。然后通过binary search 找另一个数。
It makes sense, pointer + a sorted numbers
worse case是olgn.
How can get this? |
|
b***u
发帖数: 12010 | 2 不好用吧？一个heap容易用数组表示，可用sorted array的话，root和child index的
关系不容易表达。
这题从左到右每个对后面进行binary search就行，找到N/2还没有就没了。O(nlogn). |
|
d********w
发帖数: 363 | 3 complete tree定义
a binary tree in which every level, except possibly the last, is completely
filled, and all nodes are as far left as possible.
不能使用额外的空间，
insert(int data, TreeNode root)
例如complete tree
1
2 3
4
插入节点就是成为２的右儿子
1
2 3
4 5 |
|
j********e
发帖数: 1192 | 4 写了个使用O(1)memory, O(logN * logN) (N是tree的size)的程序。
类似于binary search的算法，测试代码也在下面，应该没有大bug。
先获得树的高度h，然后比较h和root->right子树的高度+1,如果相同，
说明树最后一个节点在root->right，否则最后一个节点在root->left的子树。
#include
#include
#include
#include
using namespace std;
class Node {
private:
Node *left;
Node *right;
int value;
public:
Node() {
left = right = NULL;
value = 0;
}
Node(int v) {
left = right = NULL;
value = v;
}
int Height(Node *node) {
int h... 阅读全帖
|
|
l*********8
发帖数: 4642 | 5 应该是返回-1， 因为是非法的binary树
简单一点儿的例子
((00)) 是非法的，因为用0代替（00）后变成 (0)
((00)0) 或者 ((00)(00))才是合法的 |
|
s******o
发帖数: 2233 | 6 第四版的4.8：
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 - it does not have to start at the root.
书上的解法貌似只考虑root左边或者右边subtree里的path，比如下面这个找sum=6的就
找不出来，
2
1 3
想确认一下我的理解对不对。如果需要考虑这种情况有什么简洁点的做法？ |
|
p*****2
发帖数: 21240 | 7 只是binary tree吗？
我准备写一个。应该10几行代码能搞定把？ |
|
l*******b
发帖数: 2586 | 8 想输出那个序列得要有一个数组记录每个数值在数列中之前的那个值,所以要多开一个
数组记录这个信息吧.
每次用binary search push进去一个之后那个数之前的一个数就是这个. 写得太烂了,
有空重写一下.
class Solution {
private:
vector s;
vector pre;
int push(int k) {
if(s.empty()){
s.push_back(k);
return -1;
}
if(k >= s.back()){
s.push_back(k);
return s[s.size()-2];
}
int l = 0, r = s.size()-1, mid;
while(l < r)
... 阅读全帖 |
|
|
|
g**x
发帖数: 373 | 11 What is sibling node in Binary Tree? |
|
c*********t
发帖数: 2921 | 12 这道题没有看懂。什么是binary tree里面的sibling？俺的理解是 sibling是同一个
parent下的节点，如果是这样的话，一个parent对多只有两个children，还要弄什么
sibling呀？
是不是要把同一层的节点放到一个list里就行了？ |
|
g**x
发帖数: 373 | 13 What is sibling node in Binary Tree? |
|
c*********t
发帖数: 2921 | 14 这道题没有看懂。什么是binary tree里面的sibling？俺的理解是 sibling是同一个
parent下的节点，如果是这样的话，一个parent对多只有两个children，还要弄什么
sibling呀？
是不是要把同一层的节点放到一个list里就行了？ |
|
s********k
发帖数: 6180 | 15 fread和mmap哪个效率高？另外fread的话size是整个binary file，还是分次一点点读？ |
|
d****n
发帖数: 1637 | 16 suppose binary tree root node is "root"
and all nodes pointers are in the array of
nodes[N];
// copied from leetcode.com
Node *lca2(Node *root, Node *p, Node *q) {
if (!root) return NULL;
if (root == p || root == q) return root;
Node *L = lca2(root->left, p, q);
Node *R = lca2(root->right, p, q);
if (L && R) return root;
return L ? L : R;
}
Node *lca_aux(root, left, right )
{
if (left==right)
return lca2(left,right);
return lca2(root,lca2(root,left,right), lca_aux(... 阅读全帖 |
|
l********t
发帖数: 878 | 17 Judge small 全对
Judge large, 一共92个test case,有90个是对滴，
其中一个错误的是这个test case
{9,6,-3,#,#,-6,2,#,#,2,#,-6,-6,-6}
还有一个太长，不写了。
我自己编译运行结果是16，也是正确答案。上OJ非说我的结果是15...
leetcode，或者哪位大牛给看看？谢谢啊！
/**
* Definition for binary tree */
#include
#include
#include
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int maxValue;
int maxPathSum(TreeNode... 阅读全帖 |
|
q****m
发帖数: 177 | 18 感觉 binary tree的定义没有排除 cycle的情况阿 |
|
m*******1
发帖数: 77 | 19 Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
如果中序遍历后存起来自然是好解决，可是不满足空间要求，如何在O(1)空间做到？ |
|
r*****e
发帖数: 146 | 20 Given a binary tree, find a pair of nodes whose sum is the given target
value. Find all solutions.
Any idea to use as space as possible? thanks! :) |
|
r*****e
发帖数: 146 | 21 For BST case, time: O(N), space: O(N)
1) in-order scan the tree into an array,
2) 2sum scan the array
弱问一下，若是用get_next(), get_pre()从两边往中间扫。
具体的get_next()和get_pre()的实现是什么？
(1) 存个临时变量，以及相应的栈？ 若是如此，每次get_next()的时间是O(1),stack
takes O(N) space.
(2) 不存临时变量，每次binary search the next closest value? time is O(logN),
space is O(1)
If we adopt option (1),for bst case, time is O(N), space is O(N)
If we adopt option (2),for bst case, time is O(NlogN), space is O(1)
不知理解是否正确，请指教 |
|
c********t
发帖数: 5706 | 22 Given a binary tree, return the bottom-up level order traversal of its nodes
' values. (ie, from left to right, level by level from leaf to root).
我用层打印存入ArrayList，然后翻转ArrayList解的。大侠女侠们用没有更好的方法？ |
|
n****r
发帖数: 120 | 23 Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
这道题咋解呢？每个节点DFS？ |
|
f*****7
发帖数: 92 | 24 贴个我的，divide-and-conquer
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int globalMax = INT_MIN;
maxPathSum(root, globalMax);
return globalMax;
}
//return the max path sum INCL... 阅读全帖 |
|
|
r*****e
发帖数: 146 | 26 largest balanced subtree of a binary tree。
写一下，怎么也没对。。。大家讨论一下？ |
|
f*********m
发帖数: 726 | 27 不少方法都用到了binary search。设左右边界为l和r，边界中值为m。有些题用的是
while (l <= r),有的用的是while (l < r),m有的是m=l+(r-l)/2,有的是m=(l+r+1)/2
。挺晕的。
除了具体问题具体分析之外，有没有什么规律可循？ |
|
d**********n
发帖数: 132 | 28 刚开始编leetcode，关于check balanced binary tree，如果纯recursive，时间复杂
度太高，进而想用hashmap 存下各个node的height，减少迭代次数，可是leedcode总说
有Internal Error， 代码如下，应该没问题吧？有没有更搞笑的方法呢？
import java.lang.Math;
import java.util.HashMap;
public class Solution {
HashMap map = new HashMap();
public int getHeight(TreeNode root){
if (root==null){
return 0;
}
else
{
int height;
if (map.containsKey(root)){
height=map.get(r... 阅读全帖 |
|
c********t
发帖数: 5706 | 29 问如何求一个complete binary tree的nodes个数？ |
|
c********t
发帖数: 5706 | 30 没有固定结果啊，这是一道编程题，输入是一个complete binary tree,要求返回nodes
个数，遍历是一种方法，但是要O（n)，也没有用上complete 的特性。 |
|
j*****y
发帖数: 1071 | 31 对的，我没用 binary search.
需要改进
我觉得这个题目应该要 guarrantee 是 complete的，还需要check 是不是 complete的？
那太复杂了。 |
|
c********t
发帖数: 5706 | 32 不客气
感觉只要把你的codes里前几行
if(!root->right && layer == 1 )
{
return false;
}
加上if(root->left) nodenumber+=1就可以。
看看有没有高人给 binary的解法吧。 |
|
j*****y
发帖数: 1071 | 33 binary的解法就是一些数学逻辑难得搞清楚。 |
|
j*****y
发帖数: 1071 | 34 int numberNodes(TreeNode * root)
{
int result = 0;
int nodes = 1;
TreeNode *tmp = root;
int rightLayer = 0;
while(tmp)
{
result += nodes;
++rightLayer;
nodes *= 2;
tmp = tmp->right;
}
int leftLayer = 0;
tmp = root;
while(tmp)
{
++leftLayer;
tmp = tmp->left;
}
if(leftLayer == rightLayer)
{
return result;
}
tmp = root;
while(tmp)
{
--rightLayer;
int layer ... 阅读全帖 |
|
j*****y
发帖数: 1071 | 35 那这里的 sentinel是 null pointer ?
serialize以后要写到文件里面，这里有 struct, 那么文件里面存的是写 binary 的东
西吧？ 不是 text的 ？ |
|
G*******l
发帖数: 19 | 36 不一定要是null pointer，可以用0代表这个节点的data长度是0表示null（如果没有0
长度的value的话），如果有可以用-1，或者随便一个负数应该都行的。。
存到文件不一定是binary，举个例子：
abc
/ \
null abcdef
那在文件里就是 3abc06abcdef |
|
o********n
发帖数: 193 | 37 本不牛基本功不扎实，拿那个有巨大的重复元素的sorted array练手，我给自己的要求
不存在就直接插入，存在的话插在最后面，不允许用笨办法移动指针，想起来容易，但
下手不容易，发现和要是面试要求写recursive code，目前的功力肯定挂了。但是要用
iterative binary search，好像写起来更简单点，起码不会出大bug。
各位大牛觉得是不是这么回事？ |
|
l*******b
发帖数: 2586 | 38 square root那个binary search太难了... |
|
p*****2
发帖数: 21240 | 39
多谢你。binary search确实比较tricky，不能太着急写，得小心。 |
|
o********n
发帖数: 193 | 40 继续学习二爷难度列表里所有的binary search问题，发现难度很大，search 2D
matrix发现比powerx,y难，但二叶给的难度只有3，压力很大啊。 |
|
b****g
发帖数: 192 | 41 Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
看了leetcode的discuss，也没给出思路。而且貌似也改变树的结构了。 |
|
b****g
发帖数: 192 | 42 Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
看了leetcode的discuss，也没给出思路。而且貌似也改变树的结构了。 |
|
b*******n
发帖数: 847 | 43 谢谢！
经过你提醒我改了我的code，这回过了，发现用array的index来referecen简单多了
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector > levelOrderBottom(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > traversal;
vector path;
vector阅读全帖 |
|
c*****r
发帖数: 108 | 44 最近打算开始做leetcode了。
做到determine a binary tree is balanced 这道题的时候，发现online judge可能少
考虑了一种情况。(另外这个题目在crack上面有，4th edition 2010版本上的答案明显
错的。新的版本我没看过。)
下面是我看到leetcode论坛上的一段code（是错的）， 然而online judge pass了:
public class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) != -1;
}
private int height(TreeNode root)
{
if(root == null)
return 0;
int leftHeight = height(root.left);
if(leftHeight == -1)
return -1;
... 阅读全帖 |
|
l********7
发帖数: 30 | 45 刚才我也在看这个题，也同样迷糊了。
按照这个定义来看cc上给的那个算法是对的
LZ举的这个例子，如果定义balanced binary tree为：任意两个叶子节点的lvl必须相
差不超过1的话
是不是可以加入两个static变量在函数里，min_leaf_lvl和max_leaf_lvl记录所有叶节
点的层，遍历整个树的同时更新这两个值，最后看看是不是( max_left_lvl - min_
leaf_lvl ) <= 1 |
|
c*****r
发帖数: 108 | 46 是啊 多谢leetcode大侠了。
我找出了balanced binary tree的定义了。 它的定义是比较open的。 leaf到root的
距离不同的BTree有不同的定义。 |
|
W********e
发帖数: 45 | 47 Leetcode上的一题。Add binary。
我的解法是弄一个string c，让a和b都从尾部往前加，相加结果一共就四种情况，0,1,
2,3.我都分别作了处理。carr代表进位。把每位都从后往前记录在结果c中，最后返回c。
可是出来一个run time error：
Run Status: Runtime Error
Last executed input
"0", "0"
到底哪错了？
class Solution {
public:
string addBinary(string a, string b) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int len,i,lenA=a.length(),lenB=b.length(),carr=0;
len = lenA>lenB? lenA:lenB;
string c =lenA>lenB ? a : b;
int dig... 阅读全帖 |
|
s*****l
发帖数: 10 | 48 如果Binary Tree中有N个节点，那么只需要保存N+1个特殊字符，还是O(N)的空间复杂
度，不算too much吧。 |
|
l****i
发帖数: 2772 | 49 看到前面帖子里的面经，请教，Binary Tree Level Traversal有recursive的算法么？ |
|
n********r
发帖数: 719 | 50 之前在ubuntu上面用boost写的一些binary archive
现在在windows上面用boost读不了
deserializing exception
在ubuntu上读就没有问题
请问有什么解决方法吗？
谢谢！ |
|
