算法分析之二叉树遍历

算法相关数据结构总结：

序号	数据结构	文章
1	动态规划	动态规划之背包问题——01背包动态规划之背包问题——完全背包动态规划之打家劫舍系列问题动态规划之股票买卖系列问题动态规划之子序列问题算法（Java）——动态规划
2	数组	算法分析之数组问题
3	链表	算法分析之链表问题算法（Java）——链表
4	二叉树	算法分析之二叉树算法分析之二叉树遍历算法分析之二叉树常见问题算法（Java）——二叉树
5	哈希表	算法分析之哈希表算法（Java）——HashMap、HashSet、ArrayList
6	字符串	算法分析之字符串算法（Java）——字符串String
7	栈和队列	算法分析之栈和队列算法（Java）——栈、队列、堆
8	贪心算法	算法分析之贪心算法
9	回溯	Java实现回溯算法入门（排列+组合+子集） Java实现回溯算法进阶（搜索）
10	二分查找	算法（Java）——二分法查找
11	双指针、滑动窗口	算法（Java）——双指针算法分析之滑动窗口类问题

二叉树的基础知识已经在上一篇文章算法分析之二叉树学习过了，这篇文章主要是二叉树的遍历方式，包括递归和迭代版本。

二叉树的相关算法，如属性，操作，二叉搜索树等，请参考：算法分析之二叉树常见问题。

文章目录

- - 一、二叉树的遍历
  - 二、二叉树的递归遍历
  - - 1. 二叉树的前序遍历
    - 2. 二叉树的中序遍历
    - 3. 二叉树的后序遍历
  - 三、二叉树的迭代遍历
  - - 1. 二叉树的前序遍历
    - 2. 二叉树的中序遍历
    - 3. 二叉树的后序遍历
  - 四、二叉树的层序遍历
  - - 1. 层序遍历的迭代实现
    - 2. leetcode关于层序遍历的算法
    - - 107. 二叉树的层序遍历 II
      - 199. 二叉树的右视图

一、二叉树的遍历

二叉树的遍历方式主要有两种：

深度优先遍历（DFS）：前序、中序、后续遍历
广度优先遍历（BFS）：层序遍历

leetcode相关题目：

144. 二叉树的前序遍历

94. 二叉树的中序遍历

145. 二叉树的后序遍历

102. 二叉树的层序遍历

二、二叉树的递归遍历

先写一下递归的三要素：

确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件：写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
确定单层递归的逻辑：确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

1. 二叉树的前序遍历

前序遍历：根左右

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        // 递归版本
        ArrayList<Integer> res = new ArrayList<>();
        preOrder(root, res);
        return res;
    }

    public void preOrder(TreeNode root, ArrayList<Integer> res) {
        if(root == null) return;
        res.add(root.val);
        preOrder(root.left, res);
        preOrder(root.right, res);
    }
}

2. 二叉树的中序遍历

中序遍历：左根右

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // 递归版本
        ArrayList<Integer> res = new ArrayList<>();
        inOrder(root, res);
        return res;
    }
    public void inOrder(TreeNode root, ArrayList<Integer> res) {
        if(root == null) return;
        inOrder(root.left, res);
        res.add(root.val);
        inOrder(root.right, res);
    }
}

3. 二叉树的后序遍历

后序遍历：左右根

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        // 递归版本
        ArrayList<Integer> res = new ArrayList<>();
        postOrder(root, res);
        return res;
    }
    public void postOrder(TreeNode root, ArrayList<Integer> res) {
        if(root == null) return;
        postOrder(root.left, res);
        postOrder(root.right, res);
        res.add(root.val);
    }
}

三、二叉树的迭代遍历

用栈来迭代实现二叉树的遍历，下面是用一个统一的模板来实现前中后序的迭代遍历，前序和中序比较简单，只需要修改加入的顺序，后续遍历稍微复杂，需要判断右节点。

1. 二叉树的前序遍历

用栈来迭代实现二叉树的前序遍历：

前序遍历是根左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。这样出栈的时候才是根左右的顺序。

在这里插入图片描述

一边把根节点和左节点加入list，一边左压栈，全部入栈后，出栈找右节点，将右节点加入list

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {

        // 非递归迭代版本，栈
        ArrayList<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {  
            while(cur != null) {  // 一直左压栈
                res.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            cur = cur.right;
        }
        return res;
    }
}

2. 二叉树的中序遍历

用栈来迭代实现二叉树的中序遍历：

中序遍历是左根右。

在这里插入图片描述

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // 非递归迭代版本，栈
        ArrayList<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {  
            while(cur != null) {  // 一直左压栈
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }
}

3. 二叉树的后序遍历

用栈来迭代实现二叉树的后序遍历：

有很多写法都是把前序遍历反转来实现后序遍历，但这并不是后序遍历的迭代实现。

后序遍历稍微复杂的地方是需要设置一个节点，来保存上一个节点。遇到右节点的时候需要判断是不是上一个节点。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {        
        // 非递归，迭代版本
        ArrayList<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        TreeNode pre = null;  // 记录上一个节点，用来判断右节点是不是上一个节点
        while(cur != null || !stack.isEmpty()) {  
            while(cur != null) {  // 一直左压栈
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.peek();
            // 后续遍历左节点加入list，遇到根节点，判断有没有右节点，有加右节点，无加根节点
            // 如果是从右边返回根节点，则应该返回上层，主要判断出来是不是右子树
            if(cur.right == null || cur.right == pre) {
                res.add(cur.val);
                stack.pop();
                pre = cur;
                cur = null;
            } else {
                cur = cur.right;
            }
        }
        return res;
    }
}

四、二叉树的层序遍历

1. 层序遍历的迭代实现

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

在这里插入图片描述

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 使用队列实现层序遍历，逐层将队列元素加入到list
        if(root == null) return new ArrayList<>();
        
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int count = queue.size();
            List<Integer> list = new ArrayList<>();
            while(count > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
                count--;
            }
            res.add(list);
        }
        return res;
    }
}

leetcode_242">2. leetcode关于层序遍历的算法

107. 二叉树的层序遍历 II

leetcode题目链接：107. 二叉树的层序遍历 II

给定一个二叉树，返回其节点值自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：
给定二叉树 [3,9,20,null,null,15,7],

返回其自底向上的层序遍历为：

[
  [15,7],
  [9,20],
  [3]
]

解题思路：
这道题与 102. 二叉树的层序遍历 相同，只需要在最后输出的时候反转列表即可。

这里有几种反转列表的方法：

// 1. for循环遍历反转列表
List<List<Integer>> result = new ArrayList<>();
for (int i = res.size() - 1; i >= 0; i-- ) {
    result.add(res.get(i));
}
return result;

// 2. 利用LinkedList的addFirst()函数直接将list加到队首
LinkedList<List<Integer>> res = new LinkedList<>();
……
res.addFirst(list);

Java代码实现：

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        // 使用队列实现层序遍历，逐层将队列元素加入到list
        // 使用LinkedList的addFirst()
        LinkedList<List<Integer>> res = new LinkedList<>();
        // List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int count = queue.size();
            List<Integer> list = new ArrayList<>();
            while(count > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
                count--;
            }
            res.addFirst(list);
        }
        // // 反转列表
        // List<List<Integer>> result = new ArrayList<>();
        // for (int i = res.size() - 1; i >= 0; i-- ) {
        //     result.add(res.get(i));
        // }
        // return result;
        return res;
    }
}

199. 二叉树的右视图

leetcode题目链接：199. 二叉树的右视图

给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

在这里插入图片描述

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

Java代码实现：

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        // 使用队列实现层序遍历，逐层将队列元素加入到list
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int count = queue.size();
            for(int i = 0; i < count; i++) {
                TreeNode node = queue.poll();
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
                if(i == count - 1) {  // 将每一层的最后一个节点放入列表
                    res.add(node.val);
                }
            }
        }
        return res;
    }
}

参考：

代码随想录：二叉树的遍历

二叉树的层序遍历