题解 | #二叉搜索树与双向链表# 层序遍历 非递归

package main
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 
 * @param pRootOfTree TreeNode类 
 * @return TreeNode类
*/
func Convert(pRootOfTree *TreeNode) *TreeNode {
	if pRootOfTree == nil {
		return nil
	}

	var stack []*TreeNode
	var pre *TreeNode // 用于保存双向链表的前一个节点
	var head *TreeNode // 用于保存双向链表的头节点
	isFirst := true

	current := pRootOfTree

	for current != nil || len(stack) > 0 {
		for current != nil {
			stack = append(stack, current)
			current = current.Left
		}
		current = stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		if isFirst {
			head = current // 第一个节点作为双向链表的头节点
			pre = current
			isFirst = false
		} else {
			pre.Right = current
			current.Left = pre
			pre = current
		}

		current = current.Right
	}

	return head
}