算法-二叉树遍历

二叉树遍历

二叉树遍历有四种顺序：前序、中序、后序和层次

下面使用不同的方法去使用这四种顺序，输出二叉树遍历的结果

前序

遍历框架

直接利用我们之前说过的遍历框架

在前序位置添加逻辑即可

List<Integer> res;
public List<Integer> preOrder(TreeNode root){
    res = new ArrayList<>();
    traverse(root);
    return res;
}
public void traverse(TreeNode root) {
    if(root==null){
        return;
    }
    // 前序位置
    // 将当前节点的值放入集合中
    res.add(root.val);
    traverse(root.left);
    traverse(root.right);
}

分解问题

前序遍历：根节点 + 左子树 + 右子树

public List<Integer> preOrder(TreeNode root) {
    if(root==null){
        return;
    }
    List<Integer> list = new ArrayList<>();
    // 其实也是先序位置将值放入集合中
    list.add(root.val);
    // 将左子树的遍历结果放入集合中
    list.addAll(traverse(root.left));
    // 将右子树的遍历结果放入集合中
    list.addAll(traverse(root.right));
}

使用栈

法一

public List<Integer> preOrder(TreeNode root){
    // 用来暂存需要保存的节点
    Stack<TreeNode> stack = new Stack<>();
    // 用来保存遍历结果
    List<Integer> list = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()){
        // 如果cur不空，则一直将节点放入stack中
        // 并将其置为其左节点
        while (cur != null){
            list.add(cur.val);
            stack.push(cur);
            cur = cur.left;
        }
        // 取出栈顶元素，并将cur指向其左子树根节点
        cur = stack.pop().right;
    }
    return list;
}

法二

public List preOrder(TreeNode root){
    Stack<TreeNode> stack = new Stack<>();
    List<Integer> list = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null){
        while (cur != null){
            list.add(cur.val);
            stack.push(cur);
            cur = cur.left;
        }
        // 当栈为空或者栈顶元素的右子树不为空的时候退出循环
        while (!stack.isEmpty()&&stack.peek().right==null){
            stack.pop();
        }
        // 栈为空的时候，则退出循环
        // 反之将栈顶元素出栈，并将其右节点赋值给cur
        cur = stack.isEmpty() ? null : stack.pop().right;
    }
    return list;
}

这两种方法使用栈的区别就是

对于cur的更新方式不同，

法一是直接将栈顶元素的right赋值给cur

法二是拿到第一个出栈元素的right不为空的元素赋值给cur

两种方法都可以，但是第一种写起来更为简便

法三

public List<Integer> preorderTraversal(TreeNode root) {
    if (root == null) {
        return Collections.emptyList();
    }
    Stack<TreeNode> stack = new Stack<>();
    List<Integer> res = new ArrayList<>();
    stack.push(root);
    while (!stack.empty()) {
        TreeNode pop = stack.pop();
        res.add(pop.val);
        if (pop.right != null) {
            stack.push(pop.right);
        }
        if (pop.left != null) {
            stack.push(pop.left);
        }
    }
    return res;
}

中序

遍历框架

直接利用我们之前说过的遍历框架

在中序位置添加逻辑即可

List<Integer> res;
public List<Integer> inOrder(TreeNode root){
    res = new ArrayList<>();
    traverse(root);
    return res;
}
public void traverse(TreeNode root) {
    if(root==null){
        return;
    }
    traverse(root.left);
    // 中序位置
    // 将当前节点的值放入集合中
    res.add(root.val);
    traverse(root.right);
}

分解问题

中序遍历：左子树 + 根节点 + 右子树

public List<Integer> inOrder(TreeNode root) {
    if(root==null){
        return;
    }
    List<Integer> list = new ArrayList<>();
    // 将左子树的遍历结果放入集合中去
    list.addAll(traverse(root.left));
    // 其实也就是中序位置
    list.add(root.val);
    // 将右子树的遍历结果放入集合中去
    list.addAll(traverse(root.right));
}

使用栈

法一

public List inOrder(TreeNode root){
    // 栈中存放需要暂存的节点
    Stack<TreeNode> stack = new Stack<>();
    List<Integer> list = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()){
        while (cur != null){
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        // 将出栈元素的值放入遍历结果集中去
        // 这个时候的cur一定是其左子树遍历完了
        list.add(cur.val);
        cur = cur.right;
    }
    return list;
}

法二

public List inOrder(TreeNode root){
    Stack<TreeNode> stack = new Stack<>();
    List<Integer> list = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null){
        while (cur != null){
            stack.push(cur);
            cur = cur.left;
        }
        // 当栈为空或者栈顶元素的右子树不为空的时候退出循环
        // 循环中将出栈的栈顶元素的值放入集合中
        while (!stack.isEmpty()&&stack.peek().right==null){
            list.add(stack.pop().val);
        }
        cur = stack.isEmpty() ? null : stack.pop().right;
    }
    return list;
}

这里的两种方法的区别和前序顺序遍历的使用栈的方法的区别相同

后序

遍历框架

直接利用我们之前说过的遍历框架

在后序位置添加逻辑即可

List<Integer> res;
public List<Integer> postOrder(TreeNode root){
    res = new ArrayList<>();
    traverse(root);
    return res;
}
public void traverse(TreeNode root) {
    if(root==null){
        return;
    }
    traverse(root.left);
    traverse(root.right);
    // 后序位置
    // 将当前节点的值放入集合中
    res.add(root.val);
}

分解问题

后序遍历：左子树 + 右子树 + 根节点

public List<Integer> postOrder(TreeNode root) {
    if(root==null){
        return;
    }
    List<Integer> list = new ArrayList<>();
    // 将左子树的遍历结果放入集合中去
    list.addAll(traverse(root.left));
    // 将右子树的遍历结果放入集合中去
    list.addAll(traverse(root.right));
    // 其实也就是后序位置
    list.add(root.val);
}

使用栈

后序顺序比其他顺序特殊

它需要在左右子树都遍历完之后才可以将节点的值放入集合中

如何知道左右子树都遍历完了

这就是使用栈完成后序顺序遍历的难点

单栈标记法

public List postOrder(TreeNode root){
    Stack<TreeNode> stack = new Stack<>();
    List<Integer> list = new ArrayList<>();
    TreeNode flag = null;
    TreeNode cur = root;
    while (cur!=null||!stack.isEmpty()){
        while (cur!=null){
            stack.push(root);
            cur = cur.left;
        }
        // 不能着急出栈，因为后序位置比较特殊
        // 需要先将左右子树都处理完之后才可以处理根节点
        cur = stack.peek();
        // cur.right == null 对应右子树为空的情况
        // cur.right == flag 对应右子树已经处理完成的情况
        if(cur.right == null || flag == cur.right){
            // 当出现以上两种情况之后，则说明不需要再处理右子树了，则出栈
            flag = stack.pop();
            list.add(flag.val);
            cur = null;
            continue;
        }
        cur = cur.right;
    }
    return list;
}

双栈法

public List postOrder(TreeNode root){
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    List<Integer> list = new ArrayList<>();
    TreeNode cur = root;
    while (cur!=null || !stack1.isEmpty()){
        while (cur!=null){
            stack1.push(cur);
            stack2.push(cur);
            // 注意：这里是right
            // 根 + 右 + 左 进stack1
            // 则stack2出栈就是 左 + 右 + 根
            cur = cur.right;
        }
        cur = stack1.pop().right;
    }
    while (!stack2.isEmpty()){
        list.add(stack2.pop().val);
    }
    return list;
}

层次

队列

使用队列来暂存节点，利用其先进先出的特性来达到层次遍历的效果

法一

public List levelOrder (TreeNode root){
    // 用来暂存每一层的节点
    Queue<TreeNode> queue = new LinkedList<>();
    // 用来保存结果集
    List<Integer> list = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null){
        list.add(cur.val);
        // 如果cur有左子树，则将左子树根节点放入queue中
        if(cur.left != null){
            queue.offer(cur.left);
        }
        // 如果cur有右子树，则将左子树根节点放入queue中
        if(cur.right != null){
            queue.offer(cur.right);
        }
        // 如果队列为空，则说明遍历完毕
        // 否则取出队首元素
        cur = queue.isEmpty() ? null : queue.poll();
    }
    return list;
}

法二

public List levelOrder (TreeNode root){
    Queue<TreeNode> queue = new LinkedList<>();
    List<Integer> list = new ArrayList<>();
    queue.offer(root);
    while (!queue.isEmpty()){
        // 现在在队伍里面的就是一层的所有节点，所以直接取出所有的节点
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode cur = queue.poll();
            list.add(cur.val);
            // 把该节点的下一层节点放入队列
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
    }
    return list;
}

递归

使用递归函数来得到层次遍历结果

法一

List<List<Intger>> res;
public List<List<Integer>> levelTraverse(TreeNode root){
    res = new LinkedList<>();
    // root为第0层
    traverse(root,0);
    return res;
}
public void traverse(TreeNode root, int level){
    if(root == null){
        return;
    }
    // 如果没有这一层的集合，则添加
    if(res.get(level) == null){
        res.add(new LinkedList<Integer>());
    }
    // 得到当前层次的集合并将其加入到集合中
    res.get(level).add(root.val);
    traverse(root.left,level+1);
    traverse(root.right,level+1);
}

法二

这种方法叫尾递归

它可以被改写为层次遍历使用队列的法二

它两本质是一样的

List<List<Intger>> res;

public List<List<Integer>> levelTraverse(TreeNode root) {
    res = new LinkedList<>();
    // nodes保存着当前层次的所有节点
    List<TreeNode> nodes = new LinkedList<>();
    // 先将第一层放入集合中
    nodes.push(root);
    traverse(nodes);
    return res;
}

public void traverse(List<TreeNode> nodes) {
    if (nodes.isEmpty()) {
        return;
    }
    List<Integer> curLevel = new ArrayList<>();
    TreeNode temp;
    int size = nodes.size();
    for (int i = 0; i < size; i++) {
        temp = nodes.poll();
        curLevel.add(temp.data);
        if (temp.left != null) {
            nodes.push(temp.left);
        }
        if (temp.right != null) {
            nodes.push(temp.right);
        }
    }
    res.add(curLevel);
    traverse(nodes);
}