栈方法解leetcode之114-二叉树展开为链表

题目描述:

给你二叉树的根结点root，请你将它展开为一个单链表：展开后的单链表应该同样使用TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。展开后的单链表应该与二叉树先序遍历顺序相同。

解题思路:

1. 前序遍历
2. 前序遍历的同时，修改当前结点的Left=nil，Right为下一个前序的节点即可

golang示例代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode)  {
    if root == nil {
        return
    }
    stack := []*TreeNode{root}
    for len(stack) > 0 {
        topNode := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        if topNode.Right != nil {
            stack = append(stack, topNode.Right)
        }
        if topNode.Left != nil {
            stack = append(stack, topNode.Left)
        }
        // 左置为空
        topNode.Left = nil
        // 右设置以前序遍历的下个节点,因为是栈，所以下一个元素为栈顶元素
        if len(stack) >= 1 {
            topNode.Right = stack[len(stack) - 1]
        } else {
            topNode.Right = nil
        }
    }
}

文章目录