二叉树结点结构
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){
val=x;
}
@Override
public String toString(){
return "val: "+val;
}
}
访问函数
public void visit(TreeNode node){
System.out.print(node.val+" ");
}
先序遍历
递归
public void preOrderRecursion(TreeNode node){
if (node == null)
return;
visit(node);
preOrderRecursion(node.left);
preOrderRecursion(node.right);
}
非递归
利用栈来实现
public List<Integer> preorderTraversal(TreeNode root){
List<Integer> resultList = new ArrayList<>();
Stack<TreeNode> treeNodeStack = new Stack<>();
if (root == null)
return resultList;
treeNodeStack.push(root);
while (!treeNodeStack.isEmpty()){
TreeNode temp = treeNodeStack.pop();
if (temp!=null){
resultList.add(temp.val);//访问根节点
treeNodeStack.push(temp.right);//入栈右孩子
treeNodeStack.push(temp.left);//入栈左孩子
}
}
return resultList;
}
中序遍历
递归
public void inOrderRecursion(TreeNode node){
if(node==null) //如果结点为空则返回
return;
preOrderRecursion(node.left);//访问左孩子
visit(node);//访问根节点
preOrderRecursion(node.right);//访问右孩子
}
非递归
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while(cur!=null || !stack.empty()){
while(cur!=null){
stack.add(cur);
cur = cur.left;
}
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
return list;
}
后序遍历
/**
* 非递归后序遍历
* */
public List<Integer> postOrderNonCur(TreeNode root){
List<Integer> resultList=new ArrayList<>();
if(root==null)
return resultList;
Map<TreeNode,Integer> visitedMap=new HashMap<>();
Stack<TreeNode> toBeVisitedStack=new Stack<>();
toBeVisitedStack.push(root);
while(!toBeVisitedStack.isEmpty()){
TreeNode tempNode=toBeVisitedStack.peek(); //注意这里是peek而不是pop
if(tempNode.left==null && tempNode.right==null){ //如果没有左右孩子则访问
resultList.add(tempNode.val);
visitedMap.put(tempNode, 1);
toBeVisitedStack.pop();
continue;
}else if(!((tempNode.left!=null&&visitedMap.get(tempNode.left)==null )|| (tempNode.right!=null && visitedMap.get(tempNode.right)==null))){
//如果节点的左右孩子均已被访问
resultList.add(tempNode.val);
toBeVisitedStack.pop();
visitedMap.put(tempNode, 1);
continue;
}
if(tempNode.left!=null){
while(tempNode.left!=null && visitedMap.get(tempNode.left)==null){//左孩子没有被访问
toBeVisitedStack.push(tempNode.left);
tempNode=tempNode.left;
}
}
if(tempNode.right!=null){
if(visitedMap.get(tempNode.right)==null){//右孩子没有被访问
toBeVisitedStack.push(tempNode.right);
}
}
}
return resultList;
}
也可以用一个取巧的办法,先采用类似先序遍历,先遍历根节点再右孩子最后左孩子,再把遍历的序列逆转即可得到后序遍历
public List<Integer> postorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
List<Integer> ret = new ArrayList<>();
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node != null) {
ret.add(node.val);
stack.push(node.left);
stack.push(node.right);
}
}
Collections.reverse(ret);
return ret;
}
层序遍历
层序遍历也即宽度优先搜索,一层一层搜索,非递归代码如下:
public List<Integer> levelOrder(TreeNode root){
List<Integer>> resultList = new ArrayList<>();
if (root == null)
return resultList;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
TreeNode temp = queue.poll();
if (temp !=null){
resultList.add(temp.val);
queue.add(temp.left);
queue.add(temp.right);
}
}
return resultList;
}
或
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> resultList=new ArrayList<>();
int levelNum=0;//记录某层具有多少个节点
Queue<TreeNode> treeQueue=new LinkedList<>();
treeQueue.add(root);
while(!treeQueue.isEmpty()){
levelNum=treeQueue.size();
List<Integer> levelList=new ArrayList<>();
while(levelNum>0){
TreeNode tempNode=treeQueue.poll();
if(tempNode!=null){
levelList.add(tempNode.val);
treeQueue.add(tempNode.left);
treeQueue.add(tempNode.right);
}
levelNum--;
}
if(levelList.size()>0)
resultList.add(levelList);
}
return resultList;
}
Q.E.D.