每日一题---二叉树遍历问题

算法导论p138 10.4-2

题目要求：

给定一个n节点的二叉树，写出一个O(n)时间的递归过程，将概述每个节点的关键字输出。

利用python3来实现。

'''             18
            /\
      12  10
     /\   /\
    7  4 2  21
        /
      5
'''

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

    def __str__(self):
        return f'(root: {self.val}-[left: {self.left}, right: {self.right}])'

##递归遍历
from typing import List

from define.TreeNode import TreeNode


class Solution:
    # 前序遍历
    def getAllNodes0(self, root=TreeNode) -> List[int]:
        if not self:
            return list()
        reslist = list()
        reslist.append(root.val)
        if root:
            if root.left:
                reslist.extend(Solution.getAllNodes0(self, root.left))
            if root.right:
                reslist.extend(Solution.getAllNodes0(self, root.right))
        return reslist

    # 中序遍历
    def getAllNodes1(self, root=TreeNode) -> List[int]:
        if not self:
            return list()
        reslist = list()
        if root:
            if root.left:
                reslist.extend(Solution.getAllNodes1(self, root.left))
            reslist.append(root.val)
            if root.right:
                reslist.extend(Solution.getAllNodes1(self, root.right))
        return reslist
    # 后序遍历
    def getAllNodes2(self, root=TreeNode) -> List[int]:
        if not self:
            return list()
        reslist = list()
        if root:
            if root.left:
                reslist.extend(Solution.getAllNodes2(self, root.left))
            if root.right:
                reslist.extend(Solution.getAllNodes2(self, root.right))
            reslist.append(root.val)
        return reslist

if __name__ == '__main__':

    root = TreeNode(18)
    root.left = TreeNode(12)
    root.right = TreeNode(10)
    root.left.left = TreeNode(7)
    root.left.right = TreeNode(4)
    root.right.left = TreeNode(2)
    root.right.right = TreeNode(21)
    root.left.right.left = TreeNode(5)
    print(root)
    print(Solution.getAllNodes0(self=root, root=root))  # [18, 12, 7, 4, 5, 10, 2, 21]
    print(Solution.getAllNodes1(self=root, root=root))  # [7, 12, 5, 4, 18, 2, 10, 21]
    print(Solution.getAllNodes2(self=root, root=root))  # [7, 5, 4, 12, 2, 21, 10, 18]

二叉树的递归过程就是利用了二叉树的前序遍历、中序遍历、后序遍历。

还有另外一道题，10.4-3，使用非递归，用栈作辅助，输出二叉树的全部节点。

def getAllNodesByStack(self, root=TreeNode) -> List[int]:
    if not self:
        return []
    stack, resList = list(), []
    stack.append(self)
    while stack:
        node = stack.pop()
        resList.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return resList

使用队列实现二叉树非递归展示，广度优先：

def getAllNodesByQueue(self, root=TreeNode) -> List[int]:
    if not self:
        return []
    queue, resList = collections.deque(), []
    queue.append(self)
    while queue:
        node = queue.popleft()
        resList.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return resList