二叉树

二叉树遍历,非递归

思路

DFS的非递归实现本质上是在协调入栈、出栈和访问，三种操作的顺序。上述统一使得我们不再需要关注入栈顺序，仅需要关注出栈和访问
将对节点的访问定义为results.add(node.val);

0.模板

ArrayList<Integer> results = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
//用栈模拟递归
while (cur != null || !stack.empty()) {
    //cur当做当前根节点,不断将其入栈,新参数为左节点
   //节点为空时,接着弹栈,节点左节点为空时,先入栈马上出栈,根据右节点是否为空重复过程
    while (cur != null) {
        stack.push(cur);
        cur = cur.left;
    }
    //左子树为空,弹出该节点(pre,in-order)
    cur = stack.pop();
    // 右节点作为新的根节点进行栈操作
    cur = cur.right;
}

1.前序

private List<Integer> dfsPreOrder(TreeNode root) {
    ArrayList<Integer> results = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();

    TreeNode cur = root;
    while (cur != null || !stack.empty()) {
        while (cur != null) {
            results.add(cur.val);
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        // 转向
        cur = cur.right;
    }

    return results;
}

2.中序

private List<Integer> dfsInOrder(TreeNode root) {
    List<Integer> results = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode cur = root;
    while (cur != null || !stack.empty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        results.add(cur.val);
        cur = cur.right;
    }
    return results;
}

3.后序

private List<Integer> dfsPostOrder(TreeNode root) {
    List<Integer> results = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    
    TreeNode cur = root;
    TreeNode last = null;
    while(cur != null || !stack.empty()){
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.peek();
        if (cur.right == null || cur.right == last) {
            results.add(cur.val);
            stack.pop();
            // 记录上一个访问的节点
            // 用于判断“访问根节点之前，右子树是否已访问过”
            last = cur;
            // 表示不需要转向，继续弹栈
            cur = null;
        } else {
            cur = cur.right;
        }
    }
    
    return results;
}

4.层序遍历

public List<Integer> levelOrder(TreeNode root) {
        Deque<TreeNode> queue = new ArrayDeque<>();
        ArrayList<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        //que中装同一层的结点
        queue.addLast(root);
        while (!queue.isEmpty()){
            TreeNode cur = queue.removeFirst();
            result.add(cur.val);
            if (cur.left != null){
                queue.addLast(cur.left);
            }
            if (cur.right != null){
                queue.addLast(cur.right);
            }
        }
        return result;
    }