1. 题目描述
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
2. 示例
输入：root = [1,null,2,3]
输出：[1,2,3]
输入：root =[1,3,4,5,12,3,4,39]
输出：[1,3,5,39,12,4,3,4]
3. 思路
前序遍历，获取节点值顺序为：根=>左=>右
PS:
前序遍历（根左右）
中序遍历（左根右）
后序遍历（左右跟）
4. 遇上的问题
空间复杂度使用过多
5. 具体实现代码
自己写的代码
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func preorderTraversal(root *TreeNode) []int {
if root == nil{
return nil
}
var nodeValue []int
nodeValue = append(nodeValue,root.Val)
nodeValue = append(nodeValue,preorderTraversal(root.Left)...)
nodeValue = append(nodeValue,preorderTraversal(root.Right)...)
return nodeValue
}
6. 官方题解
func preorderTraversal(root *TreeNode) (vals []int) {
var p1, p2 *TreeNode = root, nil
for p1 != nil {
p2 = p1.Left
if p2 != nil {
for p2.Right != nil && p2.Right != p1 {
p2 = p2.Right
}
if p2.Right == nil {
vals = append(vals, p1.Val)
p2.Right = p1
p1 = p1.Left
continue
}
p2.Right = nil
} else {
vals = append(vals, p1.Val)
}
p1 = p1.Right
}
return
}
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/solution/er-cha-shu-de-qian-xu-bian-li-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
官方算法使用的是Morris 遍历，
Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其前序遍历规则总结如下：
-
新建临时节点，令该节点为 root；
-
如果当前节点的左子节点为空，将当前节点加入答案，并遍历当前节点的右子节点；
-
如果当前节点的左子节点不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点：
-
如果前驱节点的右子节点为空，将前驱节点的右子节点设置为当前节点。然后将当前节点加入答案，并将前驱节点的右子节点更新为当前节点。当前节点更新为当前节点的左子节点。
-
如果前驱节点的右子节点为当前节点，将它的右子节点重新设为空。当前节点更新为当前节点的右子节点。
-
重复步骤 2 和步骤 3，直到遍历结束。
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/solution/er-cha-shu-de-qian-xu-bian-li-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
官方的解释有点难接受，看了别的大佬是这样说的：
在讲 Morris 遍历之前，我们可以先了解一下 Morris 遍历的大体流程：
- 我们记当前节点的指针为 cur，如果 cur 所指向的节点没有左孩子，那么 cur 指针向右移动，即 cur = cur.right。
- 如果 cur 所指向的节点有左孩子，那么先找到 cur 左子树的最右的节点，并使用 mostright 指针指向该最右节点。
- 如果 mostright 所指向的节点的 right 指针为空，那么让mostright 的 right 指针指向 cur，然后cur 指针向左移动；
- 如果 mostright 所指向的节点的 right 指向 cur，那么让 right 重新指向空，然后 cur 向右移动。
参考来源于：
版权声明：本文为CSDN博主「微冷…」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_40374341/article/details/109560701
7 题目来源
Morris 遍历二叉树，有点意思~ ------swrici
