二叉树的前序,中序,后序遍历的递归与非递归实现
2017-03-31 本文已影响472人
不可思议的Mark
二叉树的遍历方式
先序遍历(Pre-Order Traversal)
指先访问根,然后访问子树的遍历方式
中序遍历(In-Order Traversal)
指先访问左(右)子树,然后访问根,最后访问右(左)子树的遍历方式
后序遍历(Post-Order Traversal)
指先访问子树,然后访问根的遍历方式
递归实现
递归遍历二叉树非常简单,这里不做赘述,先给出中序遍历的代码
/**
* 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> ans = new ArrayList<>();
if(root != null) tra(root, ans);
return ans;
}
private void tra(TreeNode node, List<Integer> ans){
if(node.left != null) tra(node.left, ans);
ans.add(node.val);
if(node.right != null) tra(node.right, ans);
}
}
先序遍历只需要将递归方法中的ans.add(node.val);放到最前面,后序遍历只需要将递归方法中的ans.add(node.val);放到最后面就行。
非递归实现
前序遍历
/**
* 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> preorderTraversal(TreeNode root) {
//用来保存结果的ArrayList.
List<Integer> ans = new ArrayList<>();
//用来存储右边节点的栈
Stack<TreeNode> rights = new Stack<>();
//遍历到的当前的节点
TreeNode node = root;
while(node != null){
//将当前节点的值先放入结果
ans.add(node.val);
//如果当前节点的右边子节点不为空,则将其压入栈
if(node.right != null){
rights.add(node.right);
}
//将当前节点置为当前节点的左节点
node = node.left;
//此时若为空,则前一步作废,将当前节点置为之前压入栈的右边的节点
if(node == null && !rights.isEmpty()){
node = rights.pop();
}
}
return ans;
}
}
中序遍历
/**
* 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> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while(node != null || !stack.empty()){
while(node != null){
stack.add(node);
node = node.left;
}
node = stack.pop();
ans.add(node.val);
node = node.right;
}
return ans;
}
}
后序遍历
/**
* 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> postorderTraversal(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
if(root == null) return ans;
stack.add(root);
while(!stack.empty()){
TreeNode node = stack.pop();
ans.addFirst(node.val);
if(node.left != null) stack.add(node.left);
if(node.right != null) stack.add(node.right);
}
return ans;
}
}