遍历：
前序遍历： 节点-左-右
使用一个栈来实现，非递归：
class Solution(object): def PReorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if not root:return [] answer=[] mystack=[root] while mystack: now=mystack.pop() answer.append(now.val) if now.right:mystack.append(now.right) if now.left:mystack.append(now.left) return answer嗯，写的麻烦了，判断非空，然后直接append就好了；
def preorderTraversal(self, root): ret = [] stack = [root] while stack: node = stack.pop() if node: ret.append(node.val) stack.append(node.right) stack.append(node.left) return ret后续遍历：左、右、结点
我的思路还是用一个栈来实现，但是这个时候 节点 应该插入在第一位。出栈顺序是 右节点，再是左节点。
class Solution(object): def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ ret = [] stack = [root] while stack: node = stack.pop() if node: ret=[node.val]+ret stack.append(node.left) stack.append(node.right) return ret中序遍历：左、节点、右 直接看的好理解的 discuss，就是设置一个标记位：
class Solution: def inorderTraversal(self, root): stack = [ (False, root) ] acc = [] while stack: flag, val = stack.pop() if val: if not flag: stack.append( (False, val.right) ) stack.append( (True, val) ) stack.append( (False, val.left) ) else: acc.append( val.val ) return acc层序遍历：
class Solution(object): def levelOrder(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ if not root: return [] ans,level=[],[root] while level: n,tem=[],[] for i in level: n.append(i.val) tem.extend([i.left,i.right]) ans.append(n) level=[j for j in tem if j] return ans从低向上的层序遍历：
class Solution(object): def levelOrderBottom(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ if not root: return [] ans,level=[],[root] while level: n,tem=[],[] for i in level: n.append(i.val) tem.extend([i.left,i.right]) ans=[n]+ans level=[j for j in tem if j] return ans新闻热点
疑难解答
