golang 刷leetcode：Morris 遍历
golang 刷leetcode：Morris 遍历
golangLeetcode
发布于 2022-08-02 19:51:02
发布于 2022-08-02 19:51:02
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
空间复杂度O（1）完成中序遍历Morries遍历
过程：
1，如果左孩子非空，让左孩子的最右节点指向根节点得到左孩子的最右节点
2，如果最右节点的右孩子节点是null，说明是第一次遍历，把它的右孩子指向根节点
3，如果最右节点的右孩子是当前节点，说明，是第二次遍历，把最右节点的右孩子指向空，即还原树
4，如果左孩子为空，将当前节点移动到右节点。
5，左孩子为空父亲节点遍历一次，第一就取值，左孩子非空由于会遍历父亲节点两次，所以第二次到达父亲节点的时候取值，就实现了中序遍历。
实现：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorderTraversal(root *TreeNode) []int {
var r[]int
for root!=nil{
if root.Left!=nil{
pre:=root.Left
for pre.Right!=nil && pre.Right!=root{
pre=pre.Right
}
if pre.Right==nil{
pre.Right=root
root=root.Left
}else{
pre.Right=nil
r=append(r,root.Val)
root=root.Right
}
}else{
r=append(r,root.Val)
root=root.Right
}
}
return r
}同理先序遍历，就是第一次到达父亲节点的时候取值
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func preorderTraversal(root *TreeNode) []int {
var r[]int
for root!=nil{
if root.Left!=nil{
pre:=root.Left
for pre.Right!=nil && pre.Right!=root{
pre=pre.Right
}
if pre.Right==nil{
r=append(r,root.Val)
pre.Right=root
root=root.Left
}else{
pre.Right=nil
root=root.Right
}
}else{
r=append(r,root.Val)
root=root.Right
}
}
return r
}后序序遍历，需要在第二次到达父亲节点的时候，逆序保存，最右孩子到父亲节点的值,遍历完后，需要保存从根节点到最右孩子的逆序：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func postorderTraversal(root *TreeNode) []int {
var r[]int
tmp:=root
for root!=nil{
if root.Left!=nil{
pre:=root.Left
for pre.Right!=nil && pre.Right!=root{
pre=pre.Right
}
if pre.Right==nil{
pre.Right=root
root=root.Left
}else{
pre.Right=nil
rv:=reverse(root.Left)
for rv!=nil{
r=append(r,rv.Val)
rv=rv.Right
}
reverse(rv)
root=root.Right
}
}else{
root=root.Right
}
}
rv:=reverse(tmp)
for rv!=nil{
r=append(r,rv.Val)
rv=rv.Right
}
reverse(rv)
return r
}
func reverse(root *TreeNode) *TreeNode{
if root==nil{
return nil
}
next:=root.Right
root.Right=nil
for next!=nil{
tmp:=next.Right
next.Right=root
root=next
next=tmp
}
return root
}本文参与?腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2022-05-20，如有侵权请联系?cloudcommunity@tencent.com 删除
本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与?腾讯云自媒体分享计划? ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读