树结构及其相关遍历(未完待续)

作者: Nick_Zuo | 来源:发表于2017-06-13 22:40 被阅读19次

    老规矩,基本概念不讲了,多看看网上的各种大牛文章。在这里说说自己观点,再拿几道例题演示下。想研究更高级的话,找个红黑树或者其他之类的去玩玩,保你酸爽!
    个人感觉还是动态规划更难搞定些!上次的动态规划

    二叉树的遍历基本上分为递归和迭代(非递归),在遍历的方式上又有些区别,首当其冲的是前中后序遍历(preorder traversal, inorder traversal, postorder travesal)然后还有深度优先遍历(Deep-First Search)和广度优先遍历(Breadth-First Search)
    分析问题先从两个方面入手吧,其一是遍历方式(前序、中序、后序、深度优先、广度优先),其二是选择递归或者非递归

    • 例1 LeetCode 145. Binary Tree Postorder Traversal
      这道题中,我们先用recursive实现吧,然后再说用iterative
      选择了递归后,再看一下用什么遍历方式。根据题意,直接选择后序遍历。
      python代码如下:
    """
    # 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]
            """
            #recursive
            res = []
            if not root: return res
            
            def post( node, res ):
                if node.left: post( node.left, res )
                if node.right: post( node.right, res )
                res.append( node.val )
                
            post( root, res )
            return res
    

    现在换成iterative方式。用这种方式基本上都是从顶到底进行遍历,所以需要记录当前node和child node,并且这些node需要按照某些顺序进出,这里采用stack可以满足要求
    再看遍历方式,分析题目中的例子得知,针对该题后序遍历就是广度优先遍历结果的反向排序
    python代码如下:

    # 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]
            """        
            #iterative
            res = []
            if not root: return res
            
            sta = [root]
            while len(sta) > 0:
                node = sta[-1]
                sta.pop()
                if node.left: sta.append( node.left )
                if node.right: sta.append( node.right )
                res.append( node.val )
                
            return res[-1::-1]
    

    有优化空间的,欢迎各位优化,欢迎交流!


    这里采用非递归吧。分析题意后,发现利用广度优先遍历(BFS)最好,我们用一个stack保存当前level的所有节点(按照广度优先顺序,每个level都是从左至右),所以每层level中,stack中最后一个节点就是我们要找的
    python代码如下:

    # 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 rightSideView(self, root):
            """
            :type root: TreeNode
            :rtype: List[int]
            """
            sta = []
            res = []
            if not root: return res
            sta.append( root )
            while len(sta) > 0:
                res.append( sta[-1].val )
                sta = [ kid for node in sta for kid in (node.left, node.right) if kid ]
            
            return res
    

    以上代码有优化空间的,欢迎各位优化,欢迎交流!
    还会接着更几题!

    相关文章

      网友评论

        本文标题:树结构及其相关遍历(未完待续)

        本文链接:https://www.haomeiwen.com/subject/wckjqxtx.html