LeetCode:用栈实现二叉树的前中后序遍历

第144题：前序遍历

package test;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}

public class Solution144 {
	public List<Integer> preorderTraversal(TreeNode root) {
		Stack<TreeNode> stack = new Stack<>();
		List<Integer> list = new ArrayList<>();
		// 如果传来的是一个空节点，则返回空数组
		if (root == null)
			return list;
		// 将根节点放入栈
		stack.push(root);
		// 当栈不为空时
		while (!stack.isEmpty()) {
			// 取出栈顶的元素
			TreeNode node = stack.pop();
			// 数组添加当前节点的值
			list.add(node.val);
			// 如果当前节点的右孩子不为空
			if (node.right != null)
				// 向栈中压入右孩子
				stack.push(node.right);
			// 如果当前节点的左孩子不为空
			if (node.left != null)
				// 向栈中压入左孩子
				stack.push(node.left);
		}
		return list;
	}
}

第145题：中序遍历

package test;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

import org.w3c.dom.Node;

class TreeNode {
    int val;
    TreeNode left;
   TreeNode right;
   TreeNode(int x) { val = x; }
 }
public class Solution145 {
	  public List<Integer> postorderTraversal(TreeNode root) {
		  Stack<TreeNode> stack=new Stack<>();
			 List<Integer> list=new LinkedList<>();
			 if(root==null)
				 return list;
			 //将root放入栈中
			 stack.push(root);
			 while(!stack.isEmpty()) {
				 //取出栈顶的元素
				 TreeNode node=stack.pop();
				 if(node.left!=null)
					 //向栈中放入当前节点的左孩子，注意，是左孩子
					 stack.push(node.left);
				 if(node.right!=null)
					 //向栈中放入当前节点的右孩子
					 stack.push(node.right);
				 //一直向链表的首部添加，逆序添加
				 list.add(0,node.val);
			 }
			 return list;
	    }
}

第94题：后序遍历

package test;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
   TreeNode right;
   TreeNode(int x) { val = x; }
 }
public class Solution94 {
	  public List<Integer> inorderTraversal(TreeNode root) {
		  Stack<TreeNode> stack=new Stack<>();
			 List<Integer> list=new LinkedList<>();
			 //cur指向root节点
			 TreeNode cur=root;
			 //注意循环条件，需要判断当前节点是否为空，如果不判断，可能会出现空指针异常
			 while(!stack.isEmpty()||cur!=null) {
				 //如果当前节点不为空，则将其压入栈，直到遍历到最左边的节点，它的左孩子为空
				 //跳到else语句当中
				 if(cur!=null)
				 {
					 stack.push(cur);
					 cur=cur.left;
				 }
				 //此时已经遍历完成所有根节点的左孩子了，此时从最左边的节点开始
				 else {
					 //第一次取出的是最左边的节点
					 cur=stack.pop();
					 //向链表中添加该节点的值
					 list.add(cur.val);
					 //看这个节点的右孩子是否为空，如果不为空，则在下一次循环中判断这个右孩子的左子树
					 //以此类推......
					 cur=cur.right;
				 }
			 }
			 return list;
	    }
}