二叉树遍历的相关算法

心已赠人 2022-12-02 13:44 183阅读 0赞

![在这里插入图片描述][2020083110235999.png_pic_center]

public class TreeNode { 
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x){ 
            val=x;
        }
    }

# 二叉树的前序遍历 #

对于图中二叉树而言其前序遍历结果为：6 2 0 1 4 5 8 9  
二叉树的前序遍历即先遍历根结点再遍历左结点最后遍历右结点，使用递归如下：

public void preOrder(TreeNode root){ 
    	if(root==null){ 
    		return;
    	}
    	System.out.println(root.val);
    	preOrder(root.left);
    	preOrder(root.right);
    }

**非递归遍历**

public void preOrder(TreeNode root){ 
    	Stack<TreeNode> treeStack = new Stack();
    	treeStack.push(root);
    	TreeNode node;
    	while(!stack.isEmpty()){ 
    		node = treeStack.pop();
    		while(node !=null){ 
    			System.out.println(node.val);
    			treeStack.push(node.right);
    			treeStack.push(node.left);
    		}
    	}	
    
    }

# 二叉树的中序遍历 #

对于二叉树的中序遍历，即先访问左结点再访问根节点最后访问右结点

public void inOrder(TreeNode root){ 
    	if(root==null){ 
    	 	return;
    	}
    	inOrder(root);
    	System.out.println(root.val);
    	inOrder(root);
    }

在上图中的二叉树，其中序遍历为：0 1 2 4 5 6 8 9  
可以看到，二叉树的中序遍历如下：  
先将根节点入栈，  
一直往其左孩子走下去，将左孩子入栈，直到该结点没有左孩子，则访问这个结点，如果这个结点有右孩子，则将其右孩子入栈，重复找左孩子的动作，这里有个要判断结点是不是已经被访问的问题。  
非递归中序遍历（效率有点低），使用map（用set貌似更合理）来判断结点是否已经被访问

public void inOrder(TreeNode root){ 
    	Stack<TreeNode> stack = new Stack();
    	TreeNode node = root;
    	while(stack.isEmpty() || node !=null){ 
    		while(node !=null){ 
    			stack.push(node);
    			node =node.left;
    		}
    		node = stack.pop();
    		System.out.println(node.val);
    		node =node.right;
    	}
    }

# 二叉树的后序遍历 #

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<List<Integer>> levelOrder(TreeNode root){ 
    	Queue<TreeNode> queue = new LinkedList();
    	queue.offer(root);
    	List<List<Integer>> res = new ArrayList();
    	TreeNode node;
    	int size = 0;
    	while(!queue.isEmpty()){ 
    		size = queue.size();
    		List<Integer> tmp = new ArrayList();
    		for(int i=0;i<size;i++){ 
    			node = queue.poll();
    			tmp.add(node.val);
    			if(node.left!=null){ 
    				queue.offer(node.left);
    			}
    			if(node.right !=null){ 
    				queue.offer(node.right);
    			}
    		}
    		if(tmp.size()>0){ 
    			res.add(tmp);
    		}
    	}
    	return res;
    
    }

[2020083110235999.png_pic_center]: /images/20221123/2c18e8ac3c284cde965291fe7a855ed6.png