145. 二叉树的前序遍历

二叉树的前序遍历

• 难度: easy
• 原始链接: https://leetcode.cn/problems/binary-tree-preorder-traversal
• 标签: 前序遍历

解法一: 递归

go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
  ans := []int{}
  var dfs func(node *TreeNode)
  dfs = func(node *TreeNode) {
    if node == nil {
      return
    }
    ans = append(ans, node.Val)
    dfs(node.Left)
    dfs(node.Right)
  }
  dfs(root)
  return ans
}

解法二: Morris 遍历

go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
  ans := []int{}
  node := root
  for node != nil {
    if node.Left != nil {
      postNode := node.Left
      for postNode.Right != nil && postNode.Right != node {
        postNode = postNode.Right
      }
      if postNode.Right == nil {
        ans = append(ans, node.Val)
        postNode.Right = node
        node = node.Left
      } else {
        node = node.Right
        postNode.Right = nil
      }
    } else {
      ans = append(ans, node.Val)
      node = node.Right
    }
  }
  return ans
}