2020-08-26:裸写算法:树的非递归先序遍历。

福大大架构师每日一题 · · 459 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

福哥答案2020-08-26:

方法 1:迭代
算法
从根节点开始,每次迭代弹出当前栈顶元素,并将其孩子节点压入栈中,先压右孩子再压左孩子。
在这个算法中,输出到最终结果的顺序按照 Top->Bottom 和 Left->Right,符合前序遍历的顺序。

算法复杂度
时间复杂度:访问每个节点恰好一次,时间复杂度为 O(N) ,其中 N 是节点的个数,也就是树的大小。
空间复杂度:取决于树的结构,最坏情况存储整棵树,因此空间复杂度是 O(N)。

方法 2:莫里斯遍历
方法基于 莫里斯的文章,可以优化空间复杂度。算法不会使用额外空间,只需要保存最终的输出结果。如果实时输出结果,那么空间复杂度是 O(1)。
算法
算法的思路是从当前节点向下访问先序遍历的前驱节点,每个前驱节点都恰好被访问两次。
首先从当前节点开始,向左孩子走一步然后沿着右孩子一直向下访问,直到到达一个叶子节点(当前节点的中序遍历前驱节点),所以我们更新输出并建立一条伪边 predecessor.Right = root 更新这个前驱的下一个点。如果我们第二次访问到前驱节点,由于已经指向了当前节点,我们移除伪边并移动到下一个顶点。
如果第一步向左的移动不存在,就直接更新输出并向右移动。

算法复杂度
时间复杂度:每个前驱恰好访问两次,因此复杂度是 O(N),其中 N 是顶点的个数,也就是树的大小。
空间复杂度:我们在计算中不需要额外空间,但是输出需要包含 N 个元素,因此空间复杂度为 O(N)。

代码用golang编写,如下:

package test34_preordertraversal

import (
    "fmt"
    "testing"
)

//https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/er-cha-shu-de-qian-xu-bian-li-by-leetcode/
//go test -v -test.run TestPreorderTraversal
func TestPreorderTraversal(t *testing.T) {
    root := &TreeNode{}
    root.Val = 1
    root.Left = &TreeNode{}
    root.Left.Val = 2
    root.Right = &TreeNode{}
    root.Right.Val = 3

    root.Left.Left = &TreeNode{}
    root.Left.Left.Val = 4
    root.Left.Right = &TreeNode{}
    root.Left.Right.Val = 5

    root.Right.Left = &TreeNode{}
    root.Right.Left.Val = 6
    root.Right.Right = &TreeNode{}
    root.Right.Right.Val = 7
    fmt.Println(preorderTraversal1(root))
    fmt.Println(preorderTraversal2(root))
}

//Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

//方法 1:迭代
//从根节点开始,每次迭代弹出当前栈顶元素,并将其孩子节点压入栈中,先压右孩子再压左孩子。
//在这个算法中,输出到最终结果的顺序按照 Top->Bottom 和 Left->Right,符合前序遍历的顺序。

//算法复杂度
//时间复杂度:访问每个节点恰好一次,时间复杂度为 O(N) ,其中 N 是节点的个数,也就是树的大小。
//空间复杂度:取决于树的结构,最坏情况存储整棵树,因此空间复杂度是 O(N)。
func preorderTraversal1(root *TreeNode) []int {
    stack := make([]*TreeNode, 0)
    output := make([]int, 0)
    if root == nil {
        return output
    }
    //push 根
    stack = append(stack, root)
    for len(stack) > 0 {
        //pop
        node := stack[len(stack)-1]
        stack = stack[0 : len(stack)-1]

        output = append(output, node.Val)
        if node.Right != nil {
            //push右
            stack = append(stack, node.Right)
        }
        if node.Left != nil {
            //push左
            stack = append(stack, node.Left)
        }
    }
    return output
}

//方法 2:莫里斯遍历
//方法基于 莫里斯的文章,可以优化空间复杂度。算法不会使用额外空间,只需要保存最终的输出结果。如果实时输出结果,那么空间复杂度是 O(1)。
//算法
//算法的思路是从当前节点向下访问先序遍历的前驱节点,每个前驱节点都恰好被访问两次。
//首先从当前节点开始,向左孩子走一步然后沿着右孩子一直向下访问,直到到达一个叶子节点(当前节点的中序遍历前驱节点),所以我们更新输出并建立一条伪边 predecessor.Right = root 更新这个前驱的下一个点。如果我们第二次访问到前驱节点,由于已经指向了当前节点,我们移除伪边并移动到下一个顶点。
//如果第一步向左的移动不存在,就直接更新输出并向右移动。

//算法复杂度
//时间复杂度:每个前驱恰好访问两次,因此复杂度是 O(N),其中 N 是顶点的个数,也就是树的大小。
//空间复杂度:我们在计算中不需要额外空间,但是输出需要包含 N 个元素,因此空间复杂度为 O(N)。
func preorderTraversal2(root *TreeNode) []int {
    output := make([]int, 0)
    node := root
    for node != nil {
        if node.Left == nil {
            //push根
            output = append(output, node.Val)
            //右
            node = node.Right
        } else {
            predecessor := node.Left
            for predecessor.Right != nil && predecessor.Right != node {
                predecessor = predecessor.Right
            }
            if predecessor.Right == nil {
                output = append(output, node.Val)
                predecessor.Right = node
                node = node.Left
            } else {
                predecessor.Right = nil
                node = node.Right
            }
        }
    }
    return output
}

敲命令 go test -v -test.run TestPreorderTraversal ,执行结果如下:


image.png

评论


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:福大大架构师每日一题

查看原文:2020-08-26:裸写算法:树的非递归先序遍历。

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

459 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传