二叉树的前中后序遍历（1）

作者: 时间煮菜 | 来源:发表于2020-03-26 16:52 被阅读0次

07-13：二叉树review1
2018-09-07
二叉树的遍历方式
POJ 2255 Tree Recovery（根据前中序遍历，重
递归调用中的递归序
数据结构与算法二叉树的遍历与线索二叉树以及森林
leetcode 144 145 94
二叉树的遍历与创建
goLang 二叉树遍历(递归非递归前序遍历中序遍历后序
树

python![1572051603644]

前序遍历

# encoding:utf-8
# Definition for a binary tree node.


class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = []  # 只用来存放根节点值
        cur = root
        res = []    # 用来存放所有结点值
        if not cur:
            return []
        while stack or cur:
            while cur:
                stack.append(cur)
                res.append(cur.val)
                cur = cur.left
            node = stack.pop()
            cur = node.right
        return res

    def preorderTraversal1(self, root):  # 递归
        res = []
        cur = root
        stack = []
        while stack or cur:
            if not cur:
                cur = stack.pop()
                cur = cur.right
            else:
                stack.append(cur)
                res.append(cur.val)
                cur = cur.left
        return res


if __name__ == "__main__":
    root = TreeNode("A")
    h1 = TreeNode("B")
    h2 = TreeNode("C")
    h3 = TreeNode("D")
    h4 = TreeNode("E")
    h5 = TreeNode("F")
    h6 = TreeNode("G")
    root.left = h1
    root.right = h2
    h1.left = h3
    h1.right = h4
    h2.left = h5
    h2.right = h6
    s = Solution()
    print s.preorderTraversal1(root)
    print s.preorderTraversal(root)

中序遍历

# encoding:utf-8
# Definition for a binary tree node.


class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = []
        cur = root
        res = []
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            node = stack.pop()
            res.append(node.val)
            cur = node.right
        return res


if __name__ == "__main__":
    root = TreeNode("A")
    h1 = TreeNode("B")
    h2 = TreeNode("C")
    h3 = TreeNode("D")
    h4 = TreeNode("E")
    h5 = TreeNode("F")
    h6 = TreeNode("G")
    root.left = h1
    root.right = h2
    h1.left = h3
    h1.right = h4
    h2.left = h5
    h2.right = h6
    s = Solution()
    print s.inorderTraversal(root)

后序遍历

# encoding:utf-8
# Definition for a binary tree node.


class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = []  # 只用来存放根节点值
        cur = root
        res = []    # 用来存放所有结点值
        last = None
        if not cur:
            return []
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            node = stack[-1]
            if node.right == None or node.right == last:
                node = stack.pop()
                last = node
                res.append(node.val)
            else:
                cur = node.right
        return res




if __name__ == "__main__":
    root = TreeNode("A")
    h1 = TreeNode("B")
    h2 = TreeNode("C")
    h3 = TreeNode("D")
    h4 = TreeNode("E")
    h5 = TreeNode("F")
    h6 = TreeNode("G")
    root.left = h1
    root.right = h2
    h1.left = h3
    h1.right = h4
    h2.left = h5
    h2.right = h6
    s = Solution()
    print s.postorderTraversal(root)