二叉树的四种遍历

二叉树三种遍历的非递归实现

利用栈来实现存储树的结构方式。

先序遍历实现步骤：

1.初始化一个栈，将头节点压入栈中。
2.弹出栈顶元素并将该点记为cur，打印该点，判断该点的右节点是否为空，不为空则入栈，判断该节点的左节点是否为空，不为空则入栈。
3.重复二步骤，直到栈中为空，遍历结束。

    def pre(self,root):
        stack = []
        res = []
        stack.append(root)
        while stack:
            cur = stack.pop()
            res.append(cur.val)
            if cur.right:
                stack.append(cur.right)
            if cur.left:
                stack.append(cur.left)
        return res

中序遍历的非递归实现：

1.初始换一个新栈，初始时，令cur=head.
2.把cur压入栈中，判断cur.left是否为空，不为空则压入栈中，然后令cur=cur.left,重复执行步骤2.
3.直到发现cur为空时，从stack中弹出一个节点，记为node,打印该节点，并让cur=node.right,然后重复步骤二。
4.当stack和cur为空，整个过程结束。

    def mid(self,root):
        res = []
        stack = []
        cur = root
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
            node = stack.pop()
            res.append(node.val)
            if node.right:
                cur = node.right
        return res

后序遍历的非递归实现：

1.初始化两个栈s1,s2，先将头节点压入栈是
中。
2.从s1中弹出元素cur，并压入到栈2中，同时如果cur的左节点存在，则将cur的左节点压入栈1，同理将cur的右节点压入栈2。
3.重复步骤二直s1为空，则栈中存放为倒序的后序遍历。

    def back(self,root):
        res = []
        s1 = []
        s2 = []
        s1.append(root)
        while s1:
            cur = s1.pop()
            s2.append(cur)
            if cur.left:
                s1.append(cur.left)
            if cur.right:
                s1.append(cur.right)
        while s2:
            res.append(s2.pop().val)
        return res

二叉树的三种递归方法实现：

先序遍历实现步骤：

    def pre(self,root,res):
        if not root:
            return 
        res.append(root.val)
        self.pre(root.left,res)
        self.pre(root.right,res)
        return res

中序序遍历实现步骤：

    def mid(self,root,res):
        if not root:
            return 
        self.mid(root.left,res)
        res.append(root.val)
        self.mid(root.right,res)
        return res

后序序遍历实现步骤：

    def back(self,root,res):
        if not root:
            return 
        self.back(root.left,res)
        self.back(root.right,res)
        res.append(root.val)
        return res

二叉树的按层遍历

按层遍历二叉树，并以数组的形式返回。

思路：

1.初始化一个队列a，将头节点压入队列中。
2.从队列中弹出元素，并打印该结点的值，同时将给节点的左孩子和右孩子压入到队列中。
3.重复上述步骤，直到队列为空。

class TreePrinter:
    def printTree(self, root):
        # write code here
        # 用一个队列来存储同一层的
        res = []
        stack = []
        stack.append(root)
        while stack:
            num = stack.pop(0)
            res.append(num.val)
            if num.left:
                stack.append(num.left)
            if num.right:
                stack.append(num.right)
        return res

案例一：有一棵二叉树，请设计一个算法，按照层次打印这棵二叉树。

给定二叉树的根结点root，请返回打印结果，结果按照每一层一个数组进行储存，所有数组的顺序按照层数从上往下，且每一层的数组内元素按照从左往右排列。保证结点数小于等于500。

思路：需要变量来表示该层是否结束，需要加入两个变量来进行追踪，last指向上一层的左右边的节点，同时nlast追踪最新的节点,同时也用队列来暂存元素每当last输出时，last指针指向最新的nlast节点

# -*- coding:utf-8 -*-

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class TreePrinter:
    def printTree(self, root):
        # write code here
        # 用一个队列来存储同一层的
        q = []
        last = root
        nlast = root
        res = []
        tmp = []
        q.append(root)
        while q:
            cur = q.pop(0)
            tmp.append(cur.val)
            if cur.left:
                q.append(cur.left)
                nlast = cur.left
            if cur.right:
                q.append(cur.right)
                nlast = cur.right
            if cur == last:
                res.append(tmp)
                tmp = []
                last = nlast
        return res