C****n
发帖数: 2324 | 1 Faint, Are you a programmer?
for (i=0;i<=n;i++)
{
TreeNode tn = new TreeNode(....);
root.Nodes.Add(tn);
for (j=0;j
tn.Nodes.Add(new TreeNode(.....));
} |
|
l*********t
发帖数: 371 | 2 这是一个很好的面试题。一般我问这个问题，我都特别看candidate是不是我跟我讨论
澄清treenode什么定义。 在面试的时候，如果问道tree的问题，你主动跟面试官沟通
，这绝对是给你加分的。 |
|
k***t
发帖数: 276 | 3 看到一个题和一个答案。不太理解。
1.What does it mean that "tree representation is in Linked list format"?
Is there a standard way to represent a tree with a linked list? Or does it
just refer to the fact that TreeNode has left and right child link/pointers.
2. "When we thread a binary tree while doing preorder traversal, it wont
result in any cycle."
Is there a standard way to "thread' a binary tree? There is no "cycle"
concept at all in normal tree traversal, isn't it?
=======================================
S... 阅读全帖 |
|
i**********e
发帖数: 1145 | 4 TreeNode 是已经定义好的了，你不用再定义。 |
|
g******p
发帖数: 18 | 5
Sorry, meant treeview control, not treenode. |
|
d**********o
发帖数: 1321 | 6 hw3b c-.y file
上面这一楼贴了载止hw3b deadline时我match的结果（也就是老师可以以这些不match
的ERROR为借口不给后来我补上的成绩），但是因为当时我还是没有写完，后来感恩节
期间就接着又写了一些，而且hw5是based on hw3 & hw3b的基础上（当我hw5是based
on更好的hw3的结果时，我应该可以得更多的分吧）。
hw4因为写得比较顺利，就不曾保留任何交上去作业的output，没有什么一目了然的结
果是我可以贴在这里的。原本我是想要把自己最的一次作业hw5贴出来的，但那已经是
一个完整的compiler，而且以后我还需要用自己的course project来找工作，所以一定
就不贴最终结果了。那就贴一个hw3b的c-.y文件吧，它集中的hw1、hw2、hw3、 hw3b的
结果，是我自己hw3b *.y文件的最完整版本。这些作业里面也有很多机关一一人为增加
的难度，比如那六七个IO相关的function，不仅traverse tree、build syntax tree的
时候会成为一个考点（把它们作为一个node连在syntax... 阅读全帖 |
|
d**********o
发帖数: 1321 | 7 hw3b c-.y file
上面这一楼贴了载止hw3b deadline时我match的结果（也就是老师可以以这些不match
的ERROR为借口不给后来我补上的成绩），但是因为当时我还是没有写完，后来感恩节
期间就接着又写了一些，而且hw5是based on hw3 & hw3b的基础上（当我hw5是based
on更好的hw3的结果时，我应该可以得更多的分吧）。
hw4因为写得比较顺利，就不曾保留任何交上去作业的output，没有什么一目了然的结
果是我可以贴在这里的。原本我是想要把自己最的一次作业hw5贴出来的，但那已经是
一个完整的compiler，而且以后我还需要用自己的course project来找工作，所以一定
就不贴最终结果了。那就贴一个hw3b的c-.y文件吧，它集中的hw1、hw2、hw3、 hw3b的
结果，是我自己hw3b *.y文件的最完整版本。这些作业里面也有很多机关一一人为增加
的难度，比如那六七个IO相关的function，不仅traverse tree、build syntax tree的
时候会成为一个考点（把它们作为一个node连在syntax... 阅读全帖 |
|
S*******C
发帖数: 822 | 8 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 ... 阅读全帖 |
|
l***h
发帖数: 96 | 9 上上周五去MTV onsite的，这周一HR说HC已经过了，等这周EC省材料，下周给我消息。
希望不要在最后一步出啥问题吧。
电面题目：
一位国人大哥，先在这里谢过啦，时间刚好45分钟，吐槽下Google docs上写程序好蛋
疼，什么时候可以搞个可以支持Vim的编辑器吧。。。。
Assume some binary (each pixel is either black or white ) images, have same
width and height, and the length is power of 2. Present it by quadtree:
divide the image into quarters, each quarter can be all back, all white or
mixed, subdivide the mixed ones… recurse.
+-------+---+---+
| | F | F |
| T +---+---+
| | T | T |
+---+---+---+---+
| F ... 阅读全帖 |
|
f******h
发帖数: 45 | 10 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
a***e
发帖数: 413 | 11 最近几天的少得可怜的准备时间都在看这个。60多行程序改个地方就通不过了。区别仅
在于
while(1)
{
r.push_back(p->val);
if(p==from)
break;
p = p->right;
}
不能改成
while(p!=from)
{
r.push_back(p->val);
p = p->right;
}
哎，可能还是因为这个算法不是自己想出来的，总是糊涂。
偶尔说起来，别人说那种属于比较偏的题了，如果问道肯定是存心要fail某人。
就是好奇有没有人真被问到。
能通过OJ的，
void reverse(TreeNode *from, TreeNode *to)
{
if (from==to)
return;
TreeNode *... 阅读全帖 |
|
S**I
发帖数: 15689 | 12 ☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 14:03:00 2011, 美东) 提到:
加recruiter一共6人
4个白男，午饭是一个组的经理 像是 土耳其／印度？ 人
除了最后一个都比较nice
另外每个人有时间都问一遍我RA做的项目，说到想吐
1. java keyword
实现浮点数的平方根，经提醒搞出来了。要考虑小于1的特殊情况； 还要想time
complexity，相对于小数点后精确位数算如何时间复杂度
2. paint fill (toggle)。关键是要考虑space complexity，主要是method stack实时
一共有多少
说了组里的相关一个问题，大概说说TRIE，有一个improvement方法不好答，他说的
用一个计算load balance function，我吐
午饭是其中一个经理，详细讲了下组里的东西，基本和我做的有点相关，感觉他们招人还是很看背景的
3. 给一个数据结构数组，（parent, child）， 重建二叉数，... 阅读全帖 |
|
e****e
发帖数: 418 | 13 Bless Louzhu.
Instead of using parentCount, use a map to record its parents. The code
might not be optimal, but it should work.
class TreeNode {
TreeNode left;
TreeNode right;
Map parentCount = new HashMap();
}
private boolean isSame(TreeNode n1, TreeNode n2, TreeNode p1, TreeNode p2) {
if ( n1 == null && n2 == null )
return true;
if ( n1 == null || n2 == null )
return false;
addParent( n1, p1 );
addParent( n2,... 阅读全帖 |
|
r*c
发帖数: 167 | 14 之前写了个C#的。思路都一样， use tree matching algorithm to determine the
candidate window.
//using System;
using System.Collections.Generic;
using System.Linq;
using System.Collections;
class MinWindowSolution
{
class TreeNode
{
public TreeNode parent;
public int val;
public List children;
public TreeNode(int i, TreeNode p) { val = i; parent = p; children =
new List(); }
};
public void FindMinWindow_Tree(int[] input, int[] query, out int nS... 阅读全帖 |
|
a***e
发帖数: 413 | 15 嗯，试图写O（1）的，发现用vector把指针装起来，再pass reference容易一些。但是
不知道为啥初始化的时候下面这个不行
vector m(2, NULL);
Compile Error
required from ‘std::vector<_Tp, _Alloc>::vector(_InputIterator, _
InputIterator, const allocator_type&) [with _InputIterator = int; _Tp =
TreeNode*; _Alloc = std::allocator; std::vector<_Tp, _Alloc>::
allocator_type = std::allocator]’
得换成这几行
vector m;
m.push_back(NULL);
m.push_back(NULL);
还没仔细debug 为什么下面这个答案不对，而后面那个就对。
错... 阅读全帖 |
|
r*c
发帖数: 167 | 16 贴个pattern字符串有重复字符的解法， 是dek,cpp1等大牛的解法的扩展。
#include
#include
#include
#include
using namespace std;
#define INT_MAX 2147483647
#define INT_MIN -2147483648
class MinWindowSolution
{
public:
struct TreeNode
{
TreeNode *parent;
int val;
vector children;
TreeNode(int i, TreeNode *p) : val(i), parent(p){}
};
void FindMinWindow_Tree(const vector& input , const vector&
query , int& nStart,... 阅读全帖 |
|
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... 阅读全帖 |
|
b******7
发帖数: 92 | 18 1)canJump
从右往左是经典dp，
f(i)表示第i+1个点跳到底n个点最小步骤
f(i) = min{1 + f(i+k)}, k = 1... A[i]
2）BST 加successor
void add_successor(TreeNode * root)
{
if(root == NULL) return NULL;
TreeNode * pre = NULL;
stack s;
for(TreeNode * p = root; p != NULL; p= p->left)
s.push(p);
while(!s.empty())
{
TreeNode * cur = s.top();
s.pop();
if(pre != NULL) pre->successor = cur;
pre = cur;
for(TreeNode * p = cur... 阅读全帖 |
|
m**********4
发帖数: 774 | 19 多谢LZ分享。试着写了一会儿，花了挺长时间才想清楚。估计要是被面肯定挂了，时间
太长要是三姐再干扰干扰根本没可能想清楚。
JAVA:
Iterative version, 应该和reverse linkedlist差不多，但要多记录几个NODE的值
public TreeNode convert(TreeNode tn){
if (tn == null)
return tn;
TreeNode curr = tn;
TreeNode prevLeft = null;
TreeNode prevRight = null;
while (curr != null){
TreeNode currLeft = curr.left;
TreeNode currRight = curr.right;
curr.left = prevRight;
... 阅读全帖 |
|
s*******s
发帖数: 1031 | 20 来自主题: JobHunting版 - 一个小面筋 做了一下，不知道对不对。
void PostVisit(TreeNode *tree) {
if(!tree)
return;
PostVisit(tree->left);
PostVisit(tree->right);
print(tree->value);
}
void PostVisit(TreeNode *tree) {
if(!tree)
return;
stack stkNodes;
stkNodes.push(tree);
while(!stkNodes.empty()) {
TreeNode *node = stkNodes.top();
if(node->left)
stkNodes.push(node->left);
else if(node->right)
stkNodes.push(node->right);
else {
... 阅读全帖 |
|
f*******t
发帖数: 7549 | 21 层序遍历+hashmap解法。动手写+test大概25分钟
public static boolean compareTrees(TreeNode tree1, TreeNode tree2) {
if (tree1 == null && tree2 == null)
return true;
else if (tree1 == null || tree2 == null)
return false;
HashMap map = new HashMap();
LinkedList list1 = new LinkedList();
LinkedList list2 = new LinkedList();
list1.add(tree1);
list2.add(tree2)... 阅读全帖 |
|
S*******C
发帖数: 822 | 22 4.9 You are given a binary tree in which each node contains a value. Design
an algorithm to print all paths which sum to a given value. The path does
not need to start or end at the root or a leaf
Page 237
他的答案如下
package Question4_9;
import CtCILibrary.TreeNode;
public class Question {
public static void findSum(TreeNode node, int sum, int[] path, int level
) {
if (node == null) {
return;
}
/* Insert current node into path */
path[level... 阅读全帖 |
|
b**********5
发帖数: 7881 | 23 求 LCA 两种情况，有parent结点跟没有parent的结点的情况都要回答。
TreeNode LCA (TreeNode a, TreeNode b) {
TreeNode aCur = a; TreeNode bCur = b;
HashSet s = new HashSet<>();
while (aCur != null || bCur != null) {
if (aCur != null) {
if (s.contains(aCur)） return aCur;
else s.add(aCur);
aCur = aCur.parent;
}
if (bCur != null) {
if (s.contains(bCur)) return bCur;
else s.add(bCur);
bCur = bCur.parent;
}
}
return nu... 阅读全帖 |
|
m****t
发帖数: 23 | 24 stack based approach
TreeNode* buildTreeStack(string &A) {
stack s_nodes;
stack s_operators;
int index = 0;
while (index
if (A[index]=='?') {
s_operators.push(A[index]);
index++;
} else if (A[index]==':') {
if (s_operators.top()=='?') {
s_operators.push(A[index]);
} else {
// pop three things from the s_no... 阅读全帖 |
|
T******7
发帖数: 1419 | 25 unique binary search II 这题目recursive解法可以么？复杂度是多少？
import java.util.ArrayList;
import java.util.List;
public class T95 {
public List generateTrees(int n) {
return genTrees(1,n);
}
public List genTrees (int start, int end)
{
List list = new ArrayList();
if(start>end)
{
list.add(null);
return list;
}
if(start == end){
list.add(new TreeNode(start));
... 阅读全帖 |
|
j********x
发帖数: 2330 | 26 我觉得是有个bug，我还没想出来怎么构造反例，先不说具体的bug了
能过small和large case
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
stack lhs;
for (TreeNode* l_root = root; l_root != NULL; l_root = l_root->left)
{
lhs.push(l_root);
}
stack rhs;
for (Tre... 阅读全帖 |
|
v*****d
发帖数: 348 | 27 为啥难写？连我这个无敌菜鸟大妈码工都能写出来啊？
public class Solution
{
public ArrayList generateTrees(int n)
{
return generateTrees(1, n);
}
public ArrayList generateTrees(int low, int high)
{
ArrayList result = new ArrayList();
if(high
{
TreeNode node = null;
result.add(node);
return result;
}
for(int i=low; i<=high; i++)
{
ArrayList<... 阅读全帖 |
|
p****6
发帖数: 724 | 28 先遍历, 边遍历边给每个节点一个index, 比如root为0, 做left减1, right加1. 然后
建立一个HashMap, key是index, value是list
贴个java版本的
public List> printVertical1(TreeNode root){
List> res = new ArrayList>();
if(root == null)
return res;
Map> map = new HashMap
TreeNode>>();
getVertical(root, map, 0);
Set keys = new TreeSet(map.keySet());
... 阅读全帖 |
|
f**********t
发帖数: 1001 | 29 最近在练习用Tree Iterator实现Tree的非递归遍历。想练习一下begin()/end()/++的
版本。code如下：
结果在operator !=那里出了问题：
Line 45: passing ‘const TreeIterator’ as ‘this’ argument of ‘TreeNode*
TreeIterator::getRoot()’ discards qualifiers [-fpermissive]
求教这个怎么fix? 多谢啦 =)
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class TreeIterator {
stack s;
TreeNode *root_;
public:
TreeN... 阅读全帖 |
|
r*****n
发帖数: 35 | 30 case class TreeNode(value: Char, var left: Option[TreeNode] = None, var
right: Option[TreeNode] = None)
object TreeBuilder {
//recursive version
def recursive(input: String, start: Int): (Int, Option[TreeNode]) ={
if (start >= input.length) {
(start, None)
} else {
val cur = Some(TreeNode(input(start)))
if (start == input.length - 1) {
(start + 1, cur)
} else {
input(start + 1) match {
case '?' =>
val (loffset, l) = recursiv... 阅读全帖 |
|
j*****u
发帖数: 1133 | 31 BST->sorted link list in C#,lz能说说这个题什么地方tricky吗？
public static ListNode BST2LinkList(TreeNode root)
{
if (root == null)
return null;
var head = new ListNode();
var tail = head;
Convert(root, ref tail);
return head.Next;
}
private static void Convert(TreeNode treeNode, ref ListNode tailNode)
{
if (treeNode != null)
{
Convert(treeNode.Left, ref tailNode);
tailNode.Next = new ListNode { Value = treeNode.Value };
tailNode = tailNode.Next;
... 阅读全帖 |
|
h*****g
发帖数: 944 | 32 谢谢大家帮我看看，我实在不知道为啥错了
#include
using namespace std;
template< class T>class TreeNode{
public:
T data;
TreeNode(T v);
TreeNode *left;
TreeNode *right;
friend ostream &operator<<(ostream &stream, TreeNode &o);
};
template TreeNode ::TreeNode(T v)
:data(v), left(NULL), right(NULL)
{
}
template ostream &operator<<(ostream &stream, TreeNode &o){
stream<data<<" ";
}
int main(){
TreeNode * head = n... 阅读全帖 |
|
b*******3
发帖数: 145 | 33 我用了两个que和1个stack，就没有多少null check，应该还可以优化。代码如下：
public boolean isSymmetric1(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if(root == null){
return true;
}else{
Queue que = new LinkedList();
Queue que1 = new LinkedList();
Stack st = new Stack();
que.add(root);
st.push(root);
whi... 阅读全帖 |
|
b*******3
发帖数: 145 | 34 我用了两个que和1个stack，就没有多少null check，应该还可以优化。代码如下：
public boolean isSymmetric1(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if(root == null){
return true;
}else{
Queue que = new LinkedList();
Queue que1 = new LinkedList();
Stack st = new Stack();
que.add(root);
st.push(root);
whi... 阅读全帖 |
|
c*****2
发帖数: 34 | 35 第一题这样做可以吗？
做pre-order traversal，如果两个node相同比较parent list是否相同。
然后递归看左右子树是否相同。
public class TreeNode {
TreeNode left;
TreeNode right;
int val;
ArrayList parents = new ArrayList();
public TreeNode(int val) {this.val = val;}
}
public boolean isIdentical(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null && t2 != null) return false;
if (t1 != null && t2 == null) return false;
if (t1.val != t2.val) return false;
... 阅读全帖 |
|
x*****0
发帖数: 452 | 36 下面是这道题的链接：
http://leetcode.com/onlinejudge#question_95
下面是我的代码：
class Solution {
private:
vector helper(int start, int end) {
if (start > end) {
return vector(1, NULL);
}
vector result;
for (int i = start; i <= end; ++i) {
vector left = helper(start, i-1);
vector right = helper(i+1, end);
for (int m = 0; m < left.size(); ++m) ... 阅读全帖 |
|
A*****o
发帖数: 284 | 37 贴个递归的完整代码,抛砖引玉了
#include
#include
#include
#include
using namespace std;
// Interview question: Rebuild a tree with DFS output with level
// A, 0, B, 1, C, 2, D, 2
struct TreeNode {
string id;
TreeNode(string a) {
id = a;
}
vector children;
};
void rebuildImpl(istringstream & iss, TreeNode *&father, string id, int
level) {
TreeNode *p = new TreeNode(id);
if (!father) {
father = p;
}
else {
... 阅读全帖 |
|
N******t
发帖数: 43 | 38 贴代码，如有错误，请私信。
/**
* Implement insert and delete in a trinary tree.
*
*/
public class TrinaryTree {
/**
* define a trinary tree's node
*
*/
static class TreeNode{
public int val; // node's value
public TreeNode left, right, mid; // represent left, right, middle
node
public TreeNode(int v){
this.val = v;
left = null;
right = null;
mid = null;
}
}
TreeNode root;
public TrinaryTre... 阅读全帖 |
|
a***e
发帖数: 413 | 39 知道要O(1)space的得用Morris Traversal。但想先写个简单的，却发现改了好几次。
1。 开始没想清楚怎么把那两个错误的node找出来
2. 应该用*& 的地方用了*。 后来发现不作为param来pass还更简单。
但这样也有很多行，等有时间写个Morris的比较下。感觉也不是那么简单啊，sigh！
class Solution {
public:
TreeNode *first, *second, *pre;
void helper(TreeNode *cur)
{
if (cur==NULL)
return;
helper(cur->left);
if (pre)
{
if (pre->val>cur->val)
{
if (first==NULL)
{
first = pre;
sec... 阅读全帖 |
|
l*******0
发帖数: 95 | 40 其实这就是一个简单的二叉树插入问题
class TreeNode {
int val;
int offset;
int smaller;
TreeNode left, right;
int leftSize;
TreeNode(int offset, int val) {this.offset = offset; this.val = val; }
}
public class CountingTree {
private TreeNode root;
TreeNode[] buffer;
public CountingTree(int size) {
buffer = new TreeNode[size];
}
public void insert(int offset, int val) {
TreeNode node = new TreeNode(offset, val);
if(root == null)... 阅读全帖 |
|
x***7
发帖数: 11 | 41
T_T打了很多字回复的时候忘记密码了。。。。然后没了。。。
线段树嘛大概这样，我们建立一个[1..n]这个区间的线段树，每个叶子节点标记为1，
其他节点的值为这个节点下面有多少个为1的叶子节点。
【查找k大】
看左子树有多少个为1的节点，如果大于等于k，那么就在左子树找。如果不到k，那么
就在右子树找k-左子树为1的叶子节点个数。
当你找到相应的叶子节点，那么他表示的区间[l,r](l == r)，l或者r就是我们要找的[
1..n]里面的第k个数啦。
【删除】
就是把那个叶子节点标记为0，其他包含这个节点的区间当然就是num--
代码上面有人也回复了的，大概差不多。
-----
我自己写了个，测了几个简单的数据，不保证是对的。
struct TreeNode {
TreeNode *left, *right;
int val;
int l, r;
TreeNode (int _l, int _r) : l(_l), r(_r), left(nullptr), right(nullptr) {
}
TreeNode (int _val,... 阅读全帖 |
|
m****t
发帖数: 23 | 42 seems recursive is the easiest. I am still trying to figure out a stack-
based approach:-)
class TreeNode{
public:
string str;
TreeNode* left;
TreeNode* right;
TreeNode(string s) {
str = s;
left = NULL;
right = NULL;
}
};
class Solution {
public:
TreeNode* buildTree(string &A, int& index) {
int index_next = A.find_first_of("?:",index);
if (index_next==string::npos) {
TreeNode* root = new TreeNode(A.substr(index));
... 阅读全帖 |
|
l******s
发帖数: 3045 | 43 public class TreeNode{
public char Val {get;set;}
public List Next {get;set;}
public TreeNode(char val) { Val = val; Next = new List(); }
}
private TreeNode buildTree(string str){
if(str.Length < 3) return null;
Stack stack = new Stack();
stack.Push(new TreeNode(str[1]));
for(int i = 2; i < str.Length - 1; i++)
if(str[i] == '('){
TreeNode newNode = new TreeNode(str[++i]);
stack.Peek().Next.Add(new... 阅读全帖 |
|
j**7
发帖数: 143 | 44 public TreeNode createTree(String s) {
Stack st = new Stack();
TreeNode root = null;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == ')') {
root = st.pop();
} else if (c >= 'A' && c <= 'Z') {
TreeNode newNode = new TreeNode(c);
if (st.isEmpty() == false) {
st.peek().children.add(newNode);
}
st.pus... 阅读全帖 |
|
h****n
发帖数: 1093 | 45 第一题，随手写了DFS和BFS，请指教
TreeNode* GetDeepestNode(TreeNode* root)
{
TreeNode* res=NULL;
int curLevel=1,preLevel=0;
DFSHelper(root, res, curLevel, preLevel);
//BFSHelper(root, res);
return res;
}
//Time O(n) space 不算递归栈则O（1） 算的话 O(lgn)
void DFSHelper(TreeNode* root, TreeNode* &res, int & curLevel, int &
preLevel)
{
if(root)
{
if(curLevel>preLevel)
{
res = root;
preLevel++;
}
curLevel++;
DFSHelper(root->right, ... 阅读全帖 |
|
b*******n
发帖数: 847 | 46 谢谢！
经过你提醒我改了我的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阅读全帖 |
|
s********x
发帖数: 914 | 47 大概是这个思路吧，没有测
public static TreeNode sortedArrayToBST(int[] a)
{
TreeNode root = new TreeNode();
int left = 0, right = a.length - 1;
Queue indexes = new LinkedList();
Queue nodes = new LinkedList();
nodes.add(root);
indexes.add(left);
indexes.add(right);
while (!indexes.isEmpty())
{
left = indexes.poll();
right = indexes.poll();
TreeNode p = nodes.poll();
int mid = left + (right - left) >>> 1;
p.setValue(a[mid]);
TreeNode leftChild = null, rightChild = nu... 阅读全帖 |
|
h*****a
发帖数: 1718 | 48 不错，不过值得注意的是这样build的tree和递归建的树形状可能是不同的。但都是
balanced。
public TreeNode buildIteratively(int[] a) {
int n = a.length;
TreeNode root = createTreeOfN(n);
Stack s = new Stack();
TreeNode cur = root;
int i=0;
while (cur != null || !s.isEmpty()) {
if (cur == null) {
cur = s.pop();
cur.val = a[i++];
cur = cur.right;
} else {
s.push(cur);
... 阅读全帖 |
|
g***3
发帖数: 2304 | 49 /**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
struct TreeNodePair {
TreeNode *front;
TreeNode *rear;
TreeNodePair(TreeNode *front1, TreeNode *rear1) : front(front1), rear(
rear1){}
};
class Solution {
public:
bool isSymmetric(TreeNode *root) {
if(root == NULL) return true;
if((root->left == NULL && root->right != NULL) ||
(r... 阅读全帖 |
|
a***e
发帖数: 413 | 50 下面这两个1.2.写法都是O（N^2)吧？为啥2说是O（N）呢？另外，看到lc上一个
discussion的iterative的解法3.https://oj.leetcode.com/discuss/2297/the-
iterative-solution-is-easier-than-you-think
时间复杂度是O（N）吧？
我看了helper的function signature能写出1，对2中用到的好多STL要搜索才能写出来
，不熟。
Binary tree和recursion现在是我最弱处，多谢！
1.
class Solution {
public:
TreeNode *buildTree(vector &preorder, vector &inorder) {
if (preorder.size()==0) return NULL;
else if (preorder.size()==1)
{
TreeNode *t = new TreeNode(preorder[0])... 阅读全帖 |
|
