笔记——树的遍历

广度优先搜索（层序遍历）可以采用队列来实现：

public List<Integer> levelOrder(TreeNode root) {

    Queue<TreeNode> queue = new LinkedList<>();  
    List<Integer> list = new ArrayList<>();  

    if (root != null) {
        queue.offer(root);  // ① 搜索起点入队
    }

    while (!queue.isEmpty()) {
        
        TreeNode head = queue.poll();
        list.add(head.val);  // ② 队列头部弹出
        
        if (head.left != null) {   
            queue.add(head.left);  // ③ 左孩子入队
        }
        if (head.right != null) {
            queue.add(head.right);  // ④ 右孩子入队
        }
    }
    return list;
}

深度优先（前、中、后序遍历）可以用栈来实现：
前序遍历

//前序遍历
public void preOrderTraveralWithStack(TreeNode root) {
    Stack stack = new Stack<>();
    TreeNode treeNode = root;
    while (treeNode != null || !stack.isEmpty()) {
        //不断往栈中压入左节点,直到左边没有左节点
        while (treeNode != null) {
            System.out.println(treeNode.val);
            stack.push(treeNode);
            treeNode = treeNode.left;
        }
        //弹栈 访问右边节点
        if (!stack.isEmpty()) {
            treeNode = stack.pop();
            treeNode = treeNode.right;
        }
    }
}

中序遍历

public void middleOrderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode treeNode = root;
    while (treeNode != null || !stack.isEmpty()) {
        //不断往栈中压入左节点,直到左边没有左节点
        while (treeNode != null) {
            stack.push(treeNode);
            treeNode = treeNode.left;
        }
        //弹栈 访问右边节点
        if (!stack.isEmpty()) {
            treeNode = stack.pop();
            System.out.println(treeNode.val);
            treeNode = treeNode.right;
        }
    }
}

后序遍历

public List<Integer> postOrderTraversal(TreeNode root) {
    LinkedList<Integer> res = new LinkedList<>();
    if (root == null) {
        return res;
    }
    LinkedList<TreeNode> stack = new LinkedList<>();
    stack.add(root);
    while (!stack.isEmpty()) {
        TreeNode pop = stack.pop();
        res.add(pop.val);
        if (pop.left != null) {
            stack.push(pop.left);
        }
        if (pop.right != null) {
            stack.push(pop.right);
        }
    }
    Collections.reverse(res);
    return res;
}