描述：
-------------------------------------------------------
前序遍历：
Given a binary tree, return the preorder traversal of its nodes' values.
给出一棵二叉树，返回其节点值的前序遍历。
样例
给出一棵二叉树 {1,#,2,3},
1
\
2
/
3
返回 [1,2,3].
----------------------------------------------------------
中序遍历：
Given a binary tree, return the inorder traversal of its nodes' values.
样例
给出二叉树 {1,#,2,3},
1
\
2
/
3
返回 [1,3,2].
------------------------------------------------------
后序遍历：
Given a binary tree, return the postorder traversal of its nodes' values.
给出一棵二叉树，返回其节点值的后序遍历。
样例
给出一棵二叉树 {1,#,2,3},
1
\
2
/
3
返回 [3,2,1]
C++解题思路：
用一个栈stack就可以解决问题，vector使用.push_back方法来将元素压入栈中。
前序：
递归一：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> sol; void recurseSol(TreeNode * root) {
if (!root) {
return;
}
sol.push_back(root->val);
recurseSol(root->left);
recurseSol(root->right);
} vector<int> preorderTraversal(TreeNode* root) {
recurseSol(root);
return sol;
}
};
非递归与递归二：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
//非递归
vector<int> preorderTraversal2(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode *p = root;
while (p || !s.empty()) {
while (p){
s.push(p);
res.push_back(p->val);
p = p->left;
}
p = s.top();
s.pop();
p = p->right;
}
return res;
}
//递归
vector<int> preorderTraversal(TreeNode* root) {
vector<int> vec1,vec2;
if (!root) {
return vec1;
}
int r = root->val;
vec1 = preorderTraversal(root->left);
vec2 = preorderTraversal(root->right); vec1.insert(vec1.begin(),r);
vec1.insert(vec1.end(),vec2.begin(),vec2.end());
return vec1;
}
};
中序：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
//非递归
vector<int> inorderTraversal2(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode *p = root;
while (p || !s.empty()) {
while (p) {
s.push(p);
p = p->left;
}
p = s.top();
s.pop();
res.push_back(p->val);
p = p->right;
}
return res;
}
//递归
vector<int> inorderTraversal(TreeNode* root) {
vector<int> vec1,vec2;
if (!root) {
return vec1;
}
vec1 = inorderTraversal(root->left);
vec1.push_back(root->val);
vec2 = inorderTraversal(root->right); vec1.insert(vec1.end(),vec2.begin(),vec2.end());
return vec1;
}
};
后序：
后序非递归采用的思路是先将二叉树排序为（根-右-左），然后利用reverse函数反转vector的序列。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
//非递归
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (!root){
return res;
}
stack<TreeNode*> s;
TreeNode *p = root;
s.push(p);
while (!s.empty()) {
p = s.top();
res.push_back(p->val);
s.pop();
if(p->left)
s.push(p->left);
if(p->right)
s.push(p->right);
}
reverse(res.begin(),res.end());
return res; } //递归
vector<int> postorderTraversal2(TreeNode* root) {
vector<int> vec1,vec2;
if (!root) {
return vec1;
}
vec1 = postorderTraversal(root->left);
vec2 = postorderTraversal(root->right); vec1.insert(vec1.end(),vec2.begin(),vec2.end());
vec1.push_back(root->val);
return vec1;
}
};
JAVA解题思路：
递归实现二叉树的遍历相对简单，如果用list存放遍历结果，每次递归使用list.addall()方法即可添加“子树”;
使用非递归实现遍历比较复杂，这里我利用栈（stack）来实现节点的存取操作，使其顺利add进入list中返回。
代码如下：
package week1; import java.awt.List;
import java.util.ArrayList;
import java.util.Stack; public class 二叉树遍历 {
/**
* Definition of TreeNode:
*/
public class TreeNode {
public int val;
public TreeNode left, right; public TreeNode(int val) {
this.val = val;
this.left = this.right = null;
}
} //==============先序遍历=======================================================
/*
* @param root: A Tree
* @return: Preorder in ArrayList which contains node values.
* 递归
*/
public ArrayList<Integer> preorderTraversal(TreeNode root) {
// write your code here
ArrayList<Integer> list = new ArrayList<Integer>();
if (root == null) return list;
list.add(root.val); //先将根节点放入
if(root.left != null) list.addAll(preorderTraversal(root.left)); //递归左子树，放入list中
if(root.right != null) list.addAll(preorderTraversal(root.right)); //递归右子树，放入list中
return list;
} /*
* @param root: A Tree
* @return: Preorder in ArrayList which contains node values.
* 非递归
*/
public ArrayList<Integer> preorderTraversal2(TreeNode root) {
// write your code here
ArrayList<Integer> res = new ArrayList<Integer>();
if(root == null) return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root); //入栈操作
while(!stack.empty()){
TreeNode node = stack.pop(); //当前节点出栈
res.add(node.val);
if(node.right != null) stack.push(node.right); //先入右子树节点，因为先进后出
if(node.left != null) stack.push(node.left);
}
return res;
} //==============中序遍历=======================================================
/**
* 递归
*/
public ArrayList<Integer> inorderTraversal(TreeNode root) {
// write your code here
ArrayList<Integer> list = new ArrayList<Integer>();
if (root == null) return list;
if(root.left != null) list.addAll(inorderTraversal(root.left));
list.add(root.val);
if(root.right != null) list.addAll(inorderTraversal(root.right));
return list;
} /**
* 非递归
*/
public ArrayList<Integer> inorderTraversal2(TreeNode root) {
// write your code here
ArrayList<Integer> res = new ArrayList<Integer>();
if(root == null) return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = root;
while(node != null || !stack.empty()){
while(node != null){ //一直遍历左子树入栈，直到左叶子节点，才开始下一步出栈
stack.push(node);
node = node.left;
}
node = stack.pop();
res.add(node.val);
node = node.right; //左-中-右
}
return res;
} //==============后序遍历=======================================================
/**
* 递归
*/
public ArrayList<Integer> postorderTraversal(TreeNode root) {
// write your code here
ArrayList<Integer> list = new ArrayList<Integer>();
if (root == null) return list;
if(root.left != null) list.addAll(postorderTraversal(root.left));
if(root.right != null) list.addAll(postorderTraversal(root.right));
list.add(root.val);
return list;
} /**
* 非递归
*/
public ArrayList<Integer> postorderTraversal2(TreeNode root) {
// write your code here
ArrayList<Integer> list = new ArrayList<Integer>();
if (root == null) return list;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.empty()){
TreeNode node = stack.pop();
list.add(0,node.val); //此方法有两个参数，第一个参数指定插入位置，第二个为插入值，这里一直在0位置插入，意思是最新插入的一直在list的最前面，之前插入的到了后面
if(node.left != null) stack.push(node.left);
if(node.right != null) stack.push(node.right);
}
return list;
}
}
至此完成二叉树的遍历。 by still