LeetCode: 144. Binary Tree Preorder Traversal

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

144. Binary Tree Preorder Traversal

LeetCode - Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

Follow up: Recursive solution is trivial, could you do it iteratively?

解题分析

凡是用递归能解决的问题，都可以使用遍历来解决。用递归来求解问题，无非就是使用了方法栈来保存相关信息。同样，可以使用 Stack 来自己动手维护这些信息。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Tree Preorder Traversal.
 * Memory Usage: 37.4 MB, less than 92.86% of Java online submissions for Binary Tree Preorder Traversal.
 */
public List<Integer> preorderTraversal(TreeNode root) {
  if (Objects.isNull(root)) {
    return Collections.emptyList();
  }
  Stack<TreeNode> stack = new Stack<>();
  stack.push(root);
  List<Integer> result = new LinkedList<>();
  while (!stack.empty()) {
    TreeNode node = stack.pop();
    result.add(node.val);
    if (Objects.nonNull(node.right)) {
      stack.push(node.right);
    }
    if (Objects.nonNull(node.left)) {
      stack.push(node.left);
    }
  }
  return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-06-14 11:30
 */
public List<Integer> preorderTraversal(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  preorderTraversal(root, result);
  return result;
}

private void preorderTraversal(TreeNode root, List<Integer> result) {
  if (root == null) {
    return;
  }
  result.add(root.val);
  preorderTraversal(root.left, result);
  preorderTraversal(root.right, result);
}

一刷
二刷
二刷（Morris遍历）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Tree Preorder Traversal.
 * Memory Usage: 37.4 MB, less than 92.86% of Java online submissions for Binary Tree Preorder Traversal.
 */
public List<Integer> preorderTraversal(TreeNode root) {
  if (Objects.isNull(root)) {
    return Collections.emptyList();
  }
  Stack<TreeNode> stack = new Stack<>();
  stack.push(root);
  List<Integer> result = new LinkedList<>();
  while (!stack.empty()) {
    TreeNode node = stack.pop();
    result.add(node.val);
    if (Objects.nonNull(node.right)) {
      stack.push(node.right);
    }
    if (Objects.nonNull(node.left)) {
      stack.push(node.left);
    }
  }
  return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-06-14 11:30
 */
public List<Integer> preorderTraversal(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  preorderTraversal(root, result);
  return result;
}

private void preorderTraversal(TreeNode root, List<Integer> result) {
  if (root == null) {
    return;
  }
  result.add(root.val);
  preorderTraversal(root.left, result);
  preorderTraversal(root.right, result);
}

1
2
3
4
5
6
7
8
9
/**
 * 有一种巧妙的方法可以在线性时间内，只占用常数空间来实现前序遍历。
 * TODO 这种方法由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」
 * 中首次提出，因此被称为 Morris 遍历。
 */
public List<Integer> preorderTraversal(TreeNode root) {
  return null;
}

迭代实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public List<Integer> preorderTraversal(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  Deque<TreeNode> stack = new LinkedList<>();
  TreeNode head = root;
  while (head != null || !stack.isEmpty()) {
    if (head != null) {
      result.add(head.val);
      if (head.right != null) {
        stack.push(head.right);
      }
      head = head.left;
    } else {
      head = stack.pop();
    }
  }
  return result;
}