前中后序遍历

  前序遍历:

        result = []
        st = [root]
        while st:
            node = st.pop(-1)
            if node.right:
                st.append(node.right)
            if node.left:
                st.append(node.left)
            result.append(node.val)
        return result

  入门代码不多解释了,这种做法就是列表后面取出一个节点,然后访问根节点(这一步在前面所以叫前序),之后将右侧节点先放入列表内,在将左侧节点放入列表内(因为你每次都是拿后面的,所以后放的先访问)。

  拒绝递归写法,这样写更容易进行扩展。

  之后就可以很方便的补上中序和后序。

  中序做法:

  中序访问是左根右,所以先从左侧一直访问到底,然后将这些节点保存在一个list中,从后面开始逐一拿出来找右侧是否有节点,如果有的话,从这个节点继续左侧访问到底。

  访问到底的做法就是在访问左,从后面拿出来每个节点就是在访问根,查找这些节点是否有右节点是访问右。

            res = []
            stack = []
            while stack or root:
                # 不断往左子树方向走,每走一次就将当前节点保存到栈中
                # 这是模拟递归的调用
                if root:
                    stack.append(root)
                    root = root.left
                else:
                    tmp = stack.pop()
                    res.append(tmp.val)
                    root = tmp.right
            return res        

  后续做法:

  很好理解,后续访问是左右根。增加的时候先加入左再加入右,如123这个树,增加的时候bag中是[2,3],访问的时候pop先出来的是3所以加入的是3的左右孩子。直到把3这棵树都遍历完才会处理2.所以结果是[1,3,3的孩子们先右后左,2,2的孩子们先右后左] 。最后我们取反,那就是[2的孩子们先左后右,2,3的孩子们先左后右,3,1],就是我们想要的左右根的顺序了。

        if not root:
            return []
        bag = [root]
        result = []
        while bag:
            node = bag.pop()
            result.append(node.val)
            if node.left:
                bag.append(node.left)
            if node.right:
                bag.append(node.right)
        return result[::-1]

 

前中后序遍历

上一篇:[Android Pro] AndroidX重构和映射


下一篇:js指定key升降序排列