笔记：关于二叉树的遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        
        LinkedList<Object> stack = new LinkedList<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            Object top = stack.pop();
            if (top == null) {
                continue;
            }

            // 如果是TreeNode类型，则依次将右节点、当前节点、左节点入栈
            // 注意，推入当前节点时，实际上是将当前节点的val值入栈，表示将当前节点标记为已读
            if (top instanceof TreeNode) {
                TreeNode node = (TreeNode) top;
                stack.push(node.right);
                stack.push(node.val);
                stack.push(node.left);
            
            // 如果是Integer类型，说明该节点已经被展开过了，此时直接将该节点的val值记录下来
            } else {
                list.add((Integer) top);
            }
        }
        return list;
    }
}

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();

        // 待处理节点初始化为root
        TreeNode cur = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        
        while (cur != null || !stack.isEmpty()) {

            // 先将待处理的二叉树最左端路径上的节点入栈
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            
            // 此时的栈顶元素就是中序遍历中真正遍历到的节点
            TreeNode top = stack.pop();
            
            // 具体的处理逻辑
            list.add(top.val);

            // 接下来需要处理原栈顶元素的右子树
            cur = top.right;
        }
        return list;
    }
}

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();

        TreeNode cur = root;
        while (cur != null) {

            // 如果当前节点的左孩子为空，则处理当前节点，然后进入右子树
            if (cur.left == null) {
                
                // 具体的处理逻辑
                list.add(cur.val);
                
                cur = cur.right;
            
            // 如果当前节点的左孩子不为空，这时候需要先进入左子树
            // 但在进入之前，我们需要先想想怎么在遍历完左子树后依然能够回到当前节点
            //     鉴于中序遍历有如下两个特点：
            //     1. 树的最右边的节点总是最后才遍历到
            //     2. 在处理了某个节点后，当前指针会指向该节点的右子节点
            // 因此可以找到左子树最右边的节点（下称前驱结点），将其right指针指向当前节点
            // 这样，在前驱节点处理完后，自然会进入前驱结点的右子树，这样就回到了当前节点
            } else {

                // 在当前节点的左子树中找到最右的节点，遇到null或当前节点就停下来
                TreeNode rightest = cur.left;
                while (rightest.right != null && rightest.right != cur) {
                    rightest = rightest.right;
                }
                
                // 若前驱节点的右孩子为空，说明当前节点的左子树还未被遍历
                // 因此将前驱结点的右孩子设置为当前节点，然后进入左子树
                if (rightest.right == null) {
                    rightest.right = cur;
                    cur = cur.left;
                
                // 若前驱节点的右孩子为当前节点，说明当前节点的左子树已经遍历完了
                // 因此将前驱节点的右孩子置为空，将二叉树恢复原貌
                // 然后处理当前节点，并进入右子树
                } else {
                    rightest.right = null;
                    
                    // 具体的处理逻辑
                    list.add(cur.val);
                    
                    cur = cur.right;
                }
            }
        }

        return list;
    }
}

2. 前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
 
        // 待处理节点初始化为root
        TreeNode cur = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
         
        while (cur != null || !stack.isEmpty()) {
 
            // 如果当前节点不为空，则先处理当前节点
            // 处理完成后需要处理左节点；但如果直接左移的话，之后就很难回到右节点了
            // 因此先将右节点入栈（也就是将右节点记录下来），然后再去处理左节点
            while (cur != null) {
                list.add(cur.val);
                stack.push(cur.right);
                cur = cur.left;
            }
             
            // 栈顶元素top是个右节点
            // 执行到这里，说明top的父节点和父节点的左节点都已经被处理完成了
            // 因此接下来需要处理top节点
            cur = stack.pop();
        }
        return list;
    }
}

3. 后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
 
        // 待处理节点初始化为root
        TreeNode cur = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        
        // 记录上次被处理完成的节点
        TreeNode pre = null;
        
        while (cur != null || !stack.isEmpty()) {
 
            // 先将待处理的二叉树最左端路径上的节点入栈
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
             
            // 栈顶元素top是个父节点
            // 执行到这里，说明top的左节点已经被处理完成了
            // 但是我们还不知道top的右节点是否被处理过，因此还需要进一步判断：
            // 1. 如果右节点是空，则相当于右节点已经处理完成
            // 2. 否则，由于后续遍历中，右节点处理完成后会立即处理父节点
            //    因此如果pre是cur的右节点，也能说明cur的右节点已经处理完成
            cur = stack.pop();
            
            // 如果右节点已经处理完成，则接下来需要处理当前节点，并更新pre为当前节点
            // 注意最后要将cur置为null，否则下次循环会误以为当前节点还未被处理过
            if (cur.right == null || cur.right == pre) {
                list.add(cur.val);
                pre = cur;
                cur = null;
            
            // 否则，当前节点还不能被处理，需要重新入栈，然后处理右节点
            } else {
                stack.push(cur);
                cur = cur.right;
            }
        }
        return list;
    }
}