LeetCode: 94. Binary Tree Inorder Traversal

友情支持

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

支付宝

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

wx jikerizhi

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

94. Binary Tree Inorder Traversal

LeetCode - Binary Tree Inorder Traversal

迭代的方式，还不是很理解，还需要再思考思考。

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

Example:

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

Output: [1,3,2]

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

一刷
二刷（递归）
二刷（栈）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public List<Integer> inorderTraversal(TreeNode root) {
  Stack<TreeNode> stack = new Stack<>();
  List<Integer> result = new LinkedList<>();
  TreeNode head = root;
  while (head != null || !stack.empty()) {
    if (head != null) {
      stack.push(head);
      head = head.left;
    } else {
      head = stack.pop();
      result.add(head.val);
      head = head.right;
    }
  }
  return result;
}
  /**
   * Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Tree Inorder Traversal.
   *
   * Memory Usage: 34.8 MB, less than 100.00% of Java online submissions for Binary Tree Inorder Traversal.
   */
  public List<Integer> inorderTraversal1(TreeNode root) {
      List<Integer> result = new ArrayList<>();
      Deque<TreeNode> stack = new LinkedList<>();
      TreeNode current = root;
      while (Objects.nonNull(current) || !stack.isEmpty()) {
          while (Objects.nonNull(current)) {
              stack.push(current);
              current = current.left;
          }
          current = stack.pop();
          result.add(current.val);
          current = current.right;
      }
      return result;
  }

  /**
   * Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Tree Inorder Traversal.
   *
   * Memory Usage: 34.7 MB, less than 100.00% of Java online submissions for Binary Tree Inorder Traversal.
   */
  public List<Integer> inorderTraversalRecursion(TreeNode root) {
      List<Integer> result = new ArrayList<>();
      inorderTraversal(root, result);
      return result;
  }

  public void inorderTraversal(TreeNode root, List<Integer> result) {
      if (Objects.isNull(root)) {
          return;
      }
      inorderTraversal(root.left, result);
      result.add(root.val);
      inorderTraversal(root.right, 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> inorderTraversal(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  inorderTraversal(root, result);
  return result;
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-06-14 11:30
 */
public List<Integer> inorderTraversal(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  Deque<TreeNode> stack = new LinkedList<>();
  TreeNode head = root;
  while (head != null || !stack.isEmpty()) {
    if (head != null) {
      stack.push(head);
      head = head.left;
    } else {
      head = stack.pop();
      result.add(head.val);
      head = head.right;
    }
  }
  return result;
}