tree.go

package LeetCode

import (
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func SecondWalk(root *TreeNode) {
	if root == nil {
		return
	}
	fmt.Println(root.Val)
	SecondWalk(root.Left)
	SecondWalk(root.Right)
}

func SecondWalk2(root *TreeNode) {
	var queue []*TreeNode
	var res []int
	if root == nil {
		return
	}
	for len(queue) != 0 || root != nil {
		for root != nil {
			res = append(res, root.Val)
			queue = append(queue, root)
			root = root.Left
		}
		node := queue[len(queue)-1]
		queue = queue[:len(queue)-1]
		root = node.Right
	}
}

func ThirdWalk2(root *TreeNode) {
	var queue []*TreeNode
	var res []int
	if root == nil {
		return
	}
	for len(queue) != 0 || root != nil {
		for root != nil {
			queue = append(queue, root)
			root = root.Left
		}
		node := queue[len(queue)-1]
		queue = queue[:len(queue)-1]
		res = append(res, node.Val)
		root = node.Right
	}
}

func LastWalk(root *TreeNode) {
	var queue []*TreeNode
	var res []int
	if root == nil {
		return
	}
	var lastVisit *TreeNode
	for len(queue) != 0 || root != nil {
		for root != nil {
			queue = append(queue, root)
			root = root.Left
		}
		node := queue[len(queue)-1]
		if node.Right == nil || node.Right == lastVisit {
			queue = queue[:len(queue)-1]
			res = append(res, node.Val)
			lastVisit = node
		} else {
			root = node.Right
		}

	}
}