LeetCode[94] Binary Tree Inorder Traversal!

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

For example:
Given binary tree {1,null,2,3},

1
\
2
/
3

return [1,3,2].

分析:

两种种方法:

  1. 递归法

    递归是最简单的。

  2. 迭代法

    迭代法比先序遍历难想一些,读者自己体会。

代码:

递归法:

public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<Integer>();
if (root != null) {
result.addAll(inorderTraversal(root.left));
result.add(root.val);
result.addAll(inorderTraversal(root.right));
}
return result;
}
}

迭代法:

public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode n = root;
while (n != null || !stack.empty()) {
while (n != null) {
stack.push(n);
n = n.left;
}
n = stack.pop();
result.add(n.val);
n = n.right;
}
return result;
}
}

欢迎关注公众号: FullStackPlan 获取更多干货

Copyright © 2016 - 2017 LBD All Rights Reserved.

访客数 : | 访问量 :