导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-94.Binary Tree Inorder Traversal

题目

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

For example:
Given binary tree {1,#,2,3} ,
 1
  \
   2
  /
 3
return [1,3,2] .

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

翻译

给出一颗二叉树,返回中序遍历序列。
例如:给出二叉树 {1, #, 2, 3}。
 1
  \
   2
  /
 3
返回 [1,3,2]。
注意:递归解法很普通,你能否用非递归方法解出?

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
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
inorderTraversal(root, res);

return res;
}

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
21
22
23
24
25
26
27
28
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
res.add(node.val);
node = node.right;
}

return res;
}
}

参考:
http://www.programcreek.com/2012/12/leetcode-solution-of-binary-tree-inorder-traversal-in-java/