My code:
import java.util.ArrayList;
import java.util.List;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (root == null)
return result;
inorderTraversal(root, result);
return result;
}
private void inorderTraversal(TreeNode root, ArrayList<Integer> result) {
if (root.left != null)
inorderTraversal(root.left, result);
result.add(root.val);
if (root.right != null)
inorderTraversal(root.right, result);
}
}
inorder 遍历 tree
基本没难度，然后还算是 Medium....
傻逼。。。
主要考的还是非递归遍历。
代码如下：
**
总结： inorder tree
**
Anyway, Good luck, Richardo!
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> ret = new ArrayList<Integer>();
if (root == null)
return ret;
Stack<TreeNode> s = new Stack<TreeNode>();
TreeNode node = root;
while (node != null) {
s.push(node);
node = node.left;
}
while (!s.isEmpty()) {
TreeNode curr = s.pop();
ret.add(curr.val);
node = curr.right;
while (node != null) {
s.push(node);
node = node.left;
}
}
return ret;
}
}
非递归实现。
一开始一直在想一个问题。
我沿着左侧一直走到最后。把最左孩子pop出来。
一切正常。
但是下一步返回父亲结点时，还会再一次把左结点压入进去。该如何让程序分别出，第一次可以压入，第二次不行。
我采用了HashSet. 很显然，这样代码可以写的很简单，但是时间，空间的效率被大大浪费。
后来参考了网址。
先写第一个循环。目的就是沿着左侧一路压入。
然后写第二个循环，开始处理刚刚的问题。
同时，如果有右孩子，则需要写个内部小循环，沿着右孩子的左侧，一路压栈。
参考网页：
http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/
Anwway, Good luck, Richardo!
My code:
/**
* Definition for a binary tree node.
* 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> ret = new ArrayList<Integer>();
if (root == null) {
return ret;
}
Stack<TreeNode> s = new Stack<TreeNode>();
TreeNode p = root;
while (p != null) {
s.push(p);
p = p.left;
}
while (!s.isEmpty()) {
TreeNode curr = s.pop();
ret.add(curr.val);
if (curr.right != null) {
curr = curr.right;
while (curr != null) {
s.push(curr);
curr = curr.left;
}
}
}
return ret;
}
}
recursion就不写了，直接写了iteration版本，看的提示。
Anyway, Good luck, Richardo! -- 09/06/2016
今天看到了一种，
时间 O(n)
空间 O(1) 的遍历方法。。。。
而且不改变原来的树结构
名字叫做， morrois traversal,
自己写了下：
My code:
/**
* Definition for a binary tree node.
* 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> ret = new ArrayList<Integer>();
if (root == null) {
return ret;
}
TreeNode curr = root;
while (curr != null) {
if (curr.left == null) {
ret.add(curr.val);
curr = curr.right;
}
else {
TreeNode pre = curr.left;
while (pre.right != null && pre.right != curr) {
pre = pre.right;
}
if (pre.right == null) {
pre.right = curr;
curr = curr.left;
}
else {
ret.add(curr.val);
pre.right = null;
curr = curr.right;
}
}
}
return ret;
}
}
reference：
http://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html
Anyway, Good luck, Richardo! -- 09/08/2016
