LeetCode 144 二叉树先序遍历

1 题目描述

给定一个二叉树，返回节点值先序遍历数组。

注：勿使用递归，请使用循环解决。

例子：

输入：[1,null,2,3]

输出：[1,2,3]

题目出处：LeetCode

2 解决思路

使用循环遍历时，按先序遍历规则，遍历根后，需先遍历其左子树，这样循环对左子树递进时，右子树暂时得不到遍历，所以需要将待遍历的右子树先记录下来，而这些右子树中，先记录的后遍历。

如下代码使用nodes slice记录待遍历的右子树，首先，将root整个认为是一个右子树放进去。

若nodes slice不为空，先取nodes slice最后一个节点，遍历其左子树，若右子树不为空，仅将右子树加入nodes slice，循环直至所有左子树遍历完成，然后进入slice的下一次循环，直至slice为空。

3 Golang实现代码

https://github.com/leileiluoluo/

func preorderTraversal(root *TreeNode) []int {
    var vals []int
    if nil == root {
        return vals
    }

    // represent for right nodes waiting for traversal
    nodes := []*TreeNode{root}
    for len(nodes) > 0 {
        node := nodes[len(nodes)-1]
        for p := node; nil != p; p = p.Left {
            vals = append(vals, p.Val)
            if node == p {
                nodes = nodes[:len(nodes)-1]
            }
            if nil != p.Right {
                nodes = append(nodes, p.Right)
            }
        }
    }
    return vals
}

LeetCode 144 二叉树先序遍历

相关文章

评论