关于tree题目recursive或者iterative做法的一个疑惑

在leetcode上看到很多tree的题目都是有recursive和iterative的两种做法，大部分时候都是想到recursive，iterative有时候很难想。想问下在面试过程中会遇到用了recursive之后要求再用iterative的情况吗？谢谢！

PS： 有没有哪些题是recursive会超时，只能用iterative的


补充内容 (2020-4-24 09:47):
楼下有好心小伙伴总结了三种遍历的iterative解法。
但其实我也想知道，除了这几个经典必背的之外，其他题目会遇到要求用iterative的时候吗

iterative的一个好处是，在你的stack会长的很长的时候相比recurisve不容易overflow.

我有个folder，里面有六种解法。。分别对应3种order对应的recursive和iterative。。没办法有的不是那么intuitive的背下来吧。。

这里是iterative的，一般不是那么明显还是需要总结一下：

1. 
   
2. # inorder iterative
   
3. class Solution:
   
4.     def inorderTraversal(self, root: TreeNode) -> List[int]:
   
5.         """DFS traversal in order implementation"""
   
6.         res = []
   
7.         stack = []
   
8.         curr = root
   
9. 
   
10.         while curr or stack:
    
11.             while curr:
    
12.                 stack.append(curr)
    
13.                 curr = curr.left
    
14. 
    
15.             curr = stack.pop()
    
16.             res.append(curr.val)
    
17. 
    
18.             curr = curr.right
    
19. 
    
20.         return res
    

复制代码

1. # preorder iterative
   
2. class Solution:
   
3.     def preorderTraversal(self, root: TreeNode) -> List[int]:
   
4.         if not root:
   
5.             return []
   
6.         res = []
   
7.         stack = [root]
   
8. 
   
9.         while stack:
   
10.             curr = stack.pop()
    
11.             if not curr:
    
12.                 continue
    
13.             res.append(curr.val)
    
14.             stack.append(curr.right)
    
15.             stack.append(curr.left)
    
16. 
    
17.         return res
    

复制代码

1. # postorder iterative
   
2. class Solution:
   
3.     def postorderTraversal(self, root: TreeNode) -> List[int]:
   
4.         if not root:
   
5.             return []
   
6.         res = []
   
7.         stack = [root]
   
8. 
   
9.         while stack:
   
10.             curr = stack.pop()
    
11.             if not curr:
    
12.                 continue
    
13.             res.append(curr.val)
    
14.             stack.append(curr.left)
    
15.             stack.append(curr.right)
    
16. 
    
17.         return res[::-1]
    

复制代码

我每次见到这次问题就想到孔乙己回字的写法

遇到过, Google 电面跟vo
面试官说让你iterate 一下，你能说no?

jun900928 发表于 2020/04/21 11:18:30
遇到过, Google 电面跟vo
面试官说让你iterate 一下，你能说no?

请问层主还记得要求iterative的是哪个序遍历吗？谢谢！

小建议inorder,preorder,postorder用两种方法implement下都要会哇

cccxxxzzzz 发表于 2020-4-22 00:20
小建议inorder,preorder,postorder用两种方法implement下都要会哇

是的我有专门记下的，谢谢你提醒！

Ken.Andrew 发表于 2020-4-22 15:22
我每次见到这次问题就想到孔乙己回字的写法

真是个奇妙的联想

前段时间面试Google，原题要求写tree的三种遍历，iterative方式。