LeetCode 94 二叉树中序遍历
1 题目描述
给定一棵二叉树，返回其节点值的中序遍历结果。
例如：
输入：[1,null,2,3]
1
\
2
/
3
输出：[1,3,2]
注：递归较简单，您可否使用循环来实现？
题目出处：LeetCode
2 解决思路
参考上图，整体来看，本算法采用多条自左上到右下的线将树根和其左子树的连接“截断”，然后将根节点依次放入一个栈里，当最左下角的根节点已压栈后，然后开始依次出栈。这样的输出顺序即是中序遍历顺序。
3 Golang实现代码
https://github.com/leileiluoluo
func inorderTraversal(root *TreeNode) []int {
if nil == root {
return []int{}
}
vals := []int{}
nodes := []*TreeNode{root}
for len(nodes) > 0 {
node := nodes[len(nodes)-1]
if nil != node.Left {
nodes = append(nodes, node.Left)
node.Left = nil
continue
}
vals = append(vals, node.Val)
nodes = nodes[:len(nodes)-1]
if nil != node.Right {
nodes = append(nodes, node.Right)
}
}
return vals
}
版权声明：该博客文章由作者通过「知识共享署名 4.0 许可证」进行授权，转载须注明文章原始链接。
相关文章
评论
正在加载评论......