深度优先搜索实现后序遍历二叉树

利用深度搜索，元素出栈的顺序就是后序遍历树的顺序。

后序遍历 获取下一个未访问结点，优先返回左子结点

public static void postorder(TreeNode root){

ArrayList stack=new ArrayList<>();

Set visited=new HashSet<>();

stack.add(root);

visited.add(root);

while (!stack.isEmpty()){

TreeNode node=getUnvisitedNode(stack.get(stack.size()-1),visited);

if(node==null){

TreeNode node1 =stack.remove(stack.size()-1);

System.out.println(node1.val);

}else {

stack.add(node);

visited.add(node);}}}

获取下一个未访问结点：

private static TreeNode getUnvisitedNode(TreeNode node, Set visited){

if (node.left!=null&&!visited.contains(node.left)){

return node.left;

}

if (node.right!=null&&!visited.contains(node.right)){

return node.right;

}

return null;

}