p*****2
发帖数: 21240 | |
h****e
发帖数: 928 | 2 我最近在做一道用parent，left, right指针前中后序遍历binary tree
的题目，觉得比通常的用left,right和stack的难一些。你做过吗？
【在 p*****2 的大作中提到】
: 有人上道题大家讨论吗？
|
l*****a
发帖数: 14598 | 3 那个比stack容易吧.
no need to do stack.push();
for stack.pop() ,just use current->parent
【在 h****e 的大作中提到】
: 我最近在做一道用parent，left, right指针前中后序遍历binary tree
: 的题目，觉得比通常的用left,right和stack的难一些。你做过吗？
|
h****e
发帖数: 928 | 4 你说的这个有用visited flag吗？
【在 l*****a 的大作中提到】
: 那个比stack容易吧.
: no need to do stack.push();
: for stack.pop() ,just use current->parent
|
l*****a
发帖数: 14598 | 5 不用啊
以前讨论国多少遍了
把你的stack solution直接翻译一下就OK
【在 h****e 的大作中提到】
: 你说的这个有用visited flag吗？
|
Z*****Z
发帖数: 723 | 6 不用，拣一个你觉得不好写的贴上来一起研究研究:)
【在 h****e 的大作中提到】
: 你说的这个有用visited flag吗？
|
Z*****Z
发帖数: 723 | 7 我刚才做了一下序列化二叉树到string然后读回来的题，递归的很好写。用stack的版本
，序列化时也很好写，但是反序列化的时候变得比较tricky，求拍或同感
【在 p*****2 的大作中提到】
: 有人上道题大家讨论吗？
|
p*****2
发帖数: 21240 | 8
这个东西我做一下练练。多谢。
【在 h****e 的大作中提到】
: 我最近在做一道用parent，left, right指针前中后序遍历binary tree
: 的题目，觉得比通常的用left,right和stack的难一些。你做过吗？
|
p*****2
发帖数: 21240 | 9 preorder这个怎么样？
def preorder(root):
n=root
while n!=None:
print n.val
if n.left!=None:
n=n.left
elif n.right!=None:
n=n.right
else:
while(n.parent!=None and (n!=n.parent.left or n.parent.right==
None)):
n=n.parent
n=n.parent
if(n!=None):
n=n.right |
l*****a
发帖数: 14598 | 10 不太对，要找到一个n.parent.right!=None的才可以用
否则。。。
【在 p*****2 的大作中提到】
: preorder这个怎么样？
: def preorder(root):
: n=root
: while n!=None:
: print n.val
: if n.left!=None:
: n=n.left
: elif n.right!=None:
: n=n.right
: else:
|
|
|
l*****a
发帖数: 14598 | 11 我打算这么写
while(1)
{
if(current->parent==NULL) return;
if(current->parent->left==current&¤t->parent->right)
{ current=current->parent->right; break; }
current=current->parent;
}
【在 l*****a 的大作中提到】
: 不太对，要找到一个n.parent.right!=None的才可以用
: 否则。。。
|
p*****2
发帖数: 21240 | 12 inorder 这个行不行
def inorder(root):
f=0
n=root
while n!=None:
if f==2:
if n.parent!=None and n==n.parent.left:
f=1
n=n.parent;
elif f==1:
print n.val
if n.right!=None:
f=0
n=n.right
else:
f=2
else:
if n.left!=None:
n=n.left
else:
f=1 |
p*****2
发帖数: 21240 | 13
刚回来。是不对。
【在 l*****a 的大作中提到】
: 不太对，要找到一个n.parent.right!=None的才可以用
: 否则。。。
|
p*****2
发帖数: 21240 | 14 postorder?
def postorder(root):
f=0
n=root
while n!=None:
if f==2:
print n.val
if n.parent!=None and n==n.parent.left:
f=1
n=n.parent
elif f==1:
if n.right!=None:
f=0
n=n.right
else:
f=2
else:
if n.left!=None:
n=n.left
else:
f=1 |
p*****2
发帖数: 21240 | 15 按照这个思路又写了一个preorder
def preorder2(root):
f=0
n=root
while n!=None:
if f==2:
if n.parent!=None and n==n.parent.left:
f=1
n=n.parent
elif f==1:
if n.right!=None:
f=0
n=n.right
else:
f=2
else:
print n.val
if n.left!=None:
n=n.left
else:
f=1 |
p*****2
发帖数: 21240 | 16
版本
这个我一会儿做一下
【在 Z*****Z 的大作中提到】
: 我刚才做了一下序列化二叉树到string然后读回来的题，递归的很好写。用stack的版本
: ，序列化时也很好写，但是反序列化的时候变得比较tricky，求拍或同感
|
l*****a
发帖数: 14598 | 17 你搞了些flag看着不舒服
i will goto leftmost, then each time call FindInOrderNext()
【在 p*****2 的大作中提到】
: inorder 这个行不行
: def inorder(root):
: f=0
: n=root
: while n!=None:
: if f==2:
: if n.parent!=None and n==n.parent.left:
: f=1
: n=n.parent;
: elif f==1:
|
p*****2
发帖数: 21240 | 18
我觉得有flag这个思路更清晰。写code不容易出错。当然前提是我写的code是对的。
【在 l*****a 的大作中提到】
: 你搞了些flag看着不舒服
: i will goto leftmost, then each time call FindInOrderNext()
|
l*****a
发帖数: 14598 | 19 你搞了些多余的东西。面试管不会让你过的///
【在 p*****2 的大作中提到】
:
: 我觉得有flag这个思路更清晰。写code不容易出错。当然前提是我写的code是对的。
|
p*****2
发帖数: 21240 | 20
啥是多余的？一个flag就多余了？哪个面试官规定不能用flag呢？
【在 l*****a 的大作中提到】
: 你搞了些多余的东西。面试管不会让你过的///
|
|
|
p*****2
发帖数: 21240 | 21
版本
这题的话，recursion面试是不是就够了？
【在 Z*****Z 的大作中提到】
: 我刚才做了一下序列化二叉树到string然后读回来的题，递归的很好写。用stack的版本
: ，序列化时也很好写，但是反序列化的时候变得比较tricky，求拍或同感
|
l*****a
发帖数: 14598 | 22 问题是不需要啊。。
【在 p*****2 的大作中提到】
:
: 版本
: 这题的话，recursion面试是不是就够了？
|
p*****2
发帖数: 21240 | 23
谁规定需要和不需要呢？空间是O(1)的就是一个变量而已，又不是O（n）的。不同的算
法，少用一个变量的算法就更好？那样说的话，你的算法还多用了循环了吧？而且
while(true)看起来也不舒服呀。我觉得多用一个变量面试不是什么问题。
【在 l*****a 的大作中提到】
: 问题是不需要啊。。
|
l*****a
发帖数: 14598 | 24 那好。你就这么做吧
我只表达我的观点
【在 p*****2 的大作中提到】
:
: 谁规定需要和不需要呢？空间是O(1)的就是一个变量而已，又不是O（n）的。不同的算
: 法，少用一个变量的算法就更好？那样说的话，你的算法还多用了循环了吧？而且
: while(true)看起来也不舒服呀。我觉得多用一个变量面试不是什么问题。
|
p*****2
发帖数: 21240 | 25
我觉得这个变量还是需要的。面试的时候问我问题，我有我的算法。这题要求不能使用
recursion和stack，这是限制。我想到了我的算法，我的算法需要一个flag来实现。我
写code实现了。基本就可以了吧？面试官会因为有另外一种算法少使用一个变量而毙掉
我？这个我不是很明白。不过你是大牛，如果我的理解有误还请指出来。
【在 l*****a 的大作中提到】
: 那好。你就这么做吧
: 我只表达我的观点
|
A**l
发帖数: 2650 | 26 这种变量确实应该尽可能少用，因为不具备可扩展性以及scalability
【在 p*****2 的大作中提到】
:
: 我觉得这个变量还是需要的。面试的时候问我问题，我有我的算法。这题要求不能使用
: recursion和stack，这是限制。我想到了我的算法，我的算法需要一个flag来实现。我
: 写code实现了。基本就可以了吧？面试官会因为有另外一种算法少使用一个变量而毙掉
: 我？这个我不是很明白。不过你是大牛，如果我的理解有误还请指出来。
|
p*****2
发帖数: 21240 | 27
不明白。能不能具体谈谈？
【在 A**l 的大作中提到】
: 这种变量确实应该尽可能少用，因为不具备可扩展性以及scalability
|
A**l
发帖数: 2650 | 28 sorry，我是从最后帖子看的，之前没看代码，以为你用了O(n)的额外变量
刚才把讨论和代码都看了一遍
不过我还是同意楼上的观点，尽可能少用额外变量，在loop里面放了这么一个状态机
是人为的把code弄复杂了，象楼上提炼出一个primitive function来简化design是值
得赞许的思维方式。
除非，你这个遍历是能够证明为效率很高的，大量使用的话可以提高performance
【在 p*****2 的大作中提到】
:
: 不明白。能不能具体谈谈？
|
p*****2
发帖数: 21240 | 29
还是不明白。我觉得这是两种算法来解决这个问题呀。我这种算法就是需要这么一个变
量才行。我想应该首先从算法上着手讨论吧？面试的时候肯定也是先说算法，然后写
code，会因为算法需要一个变量就被毙掉？如果同样的算法，当然是应该少用变量了。
这个我能明白。另外就是题目加了很多限制，不能recursion, 不能用stack, 并没有说
不能用一个变量呀。
在loop里面放了这么一个状态机
还有就是这句话什么意思呀？怎么叫人为的弄复杂了？不用这个变量根本不能完成这个
算法呀。你的意思是算法本身就很复杂？
【在 A**l 的大作中提到】
: sorry，我是从最后帖子看的，之前没看代码，以为你用了O(n)的额外变量
: 刚才把讨论和代码都看了一遍
: 不过我还是同意楼上的观点，尽可能少用额外变量，在loop里面放了这么一个状态机
: 是人为的把code弄复杂了，象楼上提炼出一个primitive function来简化design是值
: 得赞许的思维方式。
: 除非，你这个遍历是能够证明为效率很高的，大量使用的话可以提高performance
|
