0%

BinaryTreeInorderTraversal

Problem94

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

给定一二叉树,中序遍历输出

ps:preorder,inorder,postorder,前中后

Key

recursive approach

利用递归解决B树的遍历问题,这种问题的代码其实大同小异,前中后的遍历输出,只需要调整递归部分即可

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
//preorder
public void preorder(node t)
if (t != null) {
System.out.print(t.value + " ");
preorder(t.left);
preorder(t.right);
}
}
//inorder
public void inorder(node t)
{
if (t != null) {
inorder(t.left);
System.out.print(t.value + " ");
inorder(t.right);
}
}
//postorder
public void postorder(node t)
{
if (t != null) {
postorder(t.left);
postorder(t.right);
System.out.print(t.value + " ");
}
}
//leverorder

Solution

Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Tree Inorder Traversal.

Memory Usage: 37.9 MB, less than 5.11% of Java online submissions for Binary Tree Inorder Traversal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List < Integer > res = new ArrayList < > ();
inorder(root, res);
return res;
}
public void inorder(TreeNode root, List < Integer > res) {
if (root != null) {
inorder(root.left, res);
res.add(root.val);
inorder(root.right, res);
}
}
}

Complexity Analysis

  • Time complexity : O(n)O(n). The time complexity is O(n)O(n) because the recursive function is T(n) = 2 \cdot T(n/2)+1T(n)=2⋅T(n/2)+1.
  • Space complexity : The worst case space required is O(n)O(n), and in the average case it’s O(\log n)O(logn) where nn is number of nodes.

stack

solution还提供了另外一种方法通过stack pop的方式来完成:

https://leetcode.com/problems/binary-tree-inorder-traversal/solution/

Morris

同上