一、前序遍历
1.递归形式
import java.util.ArrayList;
import java.util.List;
//有返回值形式
public class Main {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result=new ArrayList ();
if(root==null){
return result;
}
result.add(root.val);
result.addAll(preorderTraversal ( root.left ));
result.addAll( preorderTraversal ( root.right));
return result;
}
}
2.非递归形式
public class Main{
class TreeNode{
char val ;
TreeNode left;
TreeNode right;
public TreeNode(char var){
this.val=val;
this.left=null;
this.right=null;
}
}
public void binaryTreePreOrderNonR(TreeNode root){
Stack<TreeNode> stack=new Stack<> ();
TreeNode cur=root;
TreeNode top=null;
while (cur!=null||!stack.empty ()){
while(cur!=null) {
System.out.print (cur.val+" " );
stack.push ( cur );
cur=cur.left;
}
top=stack.pop ();
cur=top.right;
}
}
}
二、中序遍历
1.递归形式
import java.util.ArrayList;
import java.util.List;
public class Main {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result=new ArrayList ();
if(root==null){
return result;
}
result.addAll(inorderTraversal ( root.left ));
result.add(root.val);
result.addAll( inorderTraversal ( root.right));
return result;
}
}
2.非递归形式
public class Main{
class TreeNode{
char val ;
TreeNode left;
TreeNode right;
public TreeNode(char var){
this.val=val;
this.left=null;
this.right=null;
}
}
public void binaryTreeInOrderNonR(TreeNode root){
Stack<TreeNode> stack=new Stack <> ();
TreeNode cur=root;
TreeNode top=null;
while(cur!=null||!stack.empty ()){
while(cur!=null){
stack.push ( cur );
cur=cur.left;
}
top=stack.pop ();
System.out.println (top.val );
cur=top.right;
}
}
}
三、后序遍历
1.递归形式
import java.util.ArrayList;
import java.util.List;
public class Mian {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result=new ArrayList ();
if(root==null){
return result;
}
result.addAll(postorderTraversal ( root.left ));
result.addAll( postorderTraversal ( root.right));
result.add(root.val);
return result;
}
}
2.非递归形式
public class Main{
class TreeNode{
char val ;
TreeNode left;
TreeNode right;
public TreeNode(char var){
this.val=val;
this.left=null;
this.right=null;
}
}
public void binaryTreePostOrderNonR(TreeNode root){
Stack<TreeNode> stack=new Stack <> ();
TreeNode cur=root;
TreeNode pre=null;
while (cur!=null||!stack.empty ()){
while (cur!=null) {
stack.push ( cur );
cur=cur.left;
}
cur=stack.peek ();
if(cur.right==null||cur.left==pre){
System.out.print (cur.val+" " );
stack.pop ();
pre=cur;
cur=null;
}
else{
cur=cur.right;
}
}
}
