Leetcode — 树的遍历（DFS/BFS）

1.层次遍历二叉树（102/107-易）

题目描述：逐层从左向右访问所有值。自顶向下和自底向上输出层次遍历结果。

示例：

二叉树：[3,9,20,null,null,15,7],

    3
   / 
  9  20
    /  
   15   7
自顶向下层次遍历结果：         

[
  [3],
  [9,20],
  [15,7]
]
自底向上层次遍历结果：
[
  [15,7],
  [9,20],
  [3]
]

思路：本题可使用DFS（深度搜索）和BFS（广度搜索）两种方法。

1.BFS: 每次循环（循环次数为当前队列的长度）保证当前层出队列，下一层入队列！

2.DFS: 注意：为了让递归的过程中同一层的节点放到同一个列表中，在递归时要记录每个节点的深度 level，每当进入一个递归深度需要新建一个集合存储该层元素。递归三部曲：

递归函数：实现将每层节点顺序加入该层对应的集合；
终止条件：当前节点为空；
递归逻辑：添加元素，并递归左右子树

代码:

// 1.bfs
public List> levelOrder(TreeNode root) {
    List> ret = new ArrayList();
    if (root == null) return ret;
    Queue queue = new LinkedList();
    queue.add(root);
    
    while (!queue.isEmpty()) {
        int n = queue.size();
        List level = new ArrayList();
        for (int i = 0; i > levelOrder(TreeNode root) {
    List> ret = new ArrayList();
    dfs(root, ret, 0);
    //Collections.reverse(ret);   //集合逆序
    return ret;
}

private void dfs(TreeNode root, List> ret, int level) {
    if (root == null) return;
    if (ret.size() ());
    }
    // 向某层中添加元素
    ret.get(level).add(root.val);   
    //先递归左子树
    dfs(root.left, res, level + 1);  
    dfs(root.right, res, level + 1);
}

2.二叉树的右视图（199-中）

题目描述：返回从二叉树右侧所能看到的值。

示例：

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

   1

思路：本题可使用DFS（深度搜索）和BFS（广度搜索）两种方法。

1.BFS: 套用层次遍历bfs模板，记录每层的最右边节点，即为右视图看到的节点。

2.DFS：递归实现三部曲：

递归函数：实现存储当前层的最右的一个节点。
终止条件：当前节点为空
递归逻辑：当第一次level == ret.size(),即遍历当该层的第一个元素，然后继续递归右左子树。

代码：

// 1.bfs
public List rightSideView(TreeNode root) {
    List res = new ArrayList();
    if (root == null) return res;
    Queue queue = new LinkedList();
    queue.add(root);
    while (!queue.isEmpty()) {
        int n = queue.size();
        for (int i = 0; i  rightSideView_1(TreeNode root) {
    List res = new LinkedList();
    rightSideViewHelper(root, 0, res);
    return res;
}

private void rightSideViewHelper(TreeNode root, int level, List res) {
    if (root == null) {
        return;
    }
    //res.size() 的值理解成当前在等待的层级数？？？
    //res.size() == 0, 在等待 level = 0 的第一个数
    //res.size() == 1, 在等待 level = 1 的第一个数
    //res.size() == 2, 在等待 level = 2 的第一个数
    if (level == res.size()) {
        res.add(root.val);   
    }
    rightSideViewHelper(root.right, level + 1, res);
    rightSideViewHelper(root.left, level + 1, res);
}

3. 二叉树的层平均值（637-易）

题目描述：给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

示例：

输入：
    3
   / 
  9  20
    /  
   15   7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。

思路：使用BFS套用模板，实现简单。

代码：

public List averageOfLevels(TreeNode root) {
    List ret = new ArrayList();
    Queue queue = new LinkedList();
    queue.add(root);
    while (!queue.isEmpty()) {
        double sum = 0;     //每层节点值累加和
        int n = queue.size();
        for (int i = 0; i

4.得到树左下角节点（513-中）

题目描述：给定一个二叉树，在树的最后一行找到最左边的值。

示例：

思路：本题关键问题：找到最后一行和最左边节点

1. BFS: 与题199思路类似，依次更新左边界的元素（自顶向下），直到到达最后一层。

2. DFS: 最后一行：**整棵树中叶子节点的最大深度max**；最左边节点：**保证遍历时，对应的左节点先于右节点**。即递归逻辑为：递归层第一次大于当前层，即每层的第一个元素。

代码：

// 1. BFS
public int findBottomLeftValue(TreeNode root) {
    Queue queue = new LinkedList();
    int res = root.val;
    queue.add(root);
    while (!queue.isEmpty()) {
        int n = queue.size();
        for (int i = 0; i  max) {  
        max = num;
        res = node.val; 
    }
    dfs(node.left, num + 1);
    dfs(node.right, num + 1);
}

5.N叉树的层序遍历（429-中）

题目描述：给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例：

image.png

输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]

//多叉树节点定义
class Node {
    public int val;
    public List children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List _children) {
        val = _val;
        children = _children;
    }
};

思路：使用bfs，注意每次加入节点的所有孩子节点，使用addAll()方法。

代码

// bfs
public List> levelOrder(Node root) {
    List> ret = new ArrayList();
    if (root == null) return ret;
    Queue queue = new LinkedList();
    queue.add(root);
    
    while (!queue.isEmpty()) {
        int n = queue.size();
        List level = new ArrayList();
        for (int i = 0; i

6.之字形层序遍历（103-中）

题目描述：锯齿形层序遍历二叉树。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例：

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

    3
   / 
  9  20
    /  
   15   7
返回锯齿形层序遍历如下：

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

思路：

1.BFS: 实现比较简单，只不过在一行结束后加一个判断；奇数行正序存储，偶数行倒叙存储。

2.DFS: 循环遍历递归层次求解的结果，对这个结果进行处理，倒叙偶数位置的子集合。

代码：

public List> zigzagLevelOrder(TreeNode root) {
    List> ret = new ArrayList();
    if (root == null) return ret;
    Queue queue = new LinkedList();
    queue.add(root);
    int count = 0;
    
    while (!queue.isEmpty()) {
        List level = new ArrayList();
        int n = queue.size();
        count++;
        for (int i = 0; i > zigzagLevelOrder_1(TreeNode root) {
    List> ret = new ArrayList();
    dfs(ret, root, 0);
    //倒叙奇数行
    for (int i = 1; i > ret, TreeNode root, int level) {
    if (root == null) return;
    if (ret.size() ());
    }
    //ret的指定层加入值
    ret.get(level).add(root.val);  
    dfs(ret, root.left, level + 1);
    dfs(ret, root.right, level + 1);
}

7.对称二叉树（101 – 易）

题目描述：给定一个二叉树，检查它是否是镜像对称的。

示例 :

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / 
  2   2
 /  / 
3  4 4  3

思路：使用迭代和递归解决。

法1：广度优先搜索，注意队列中弹出两个数都为null，则继续判断队列中的其他元素。

ps：remove和poll都是返回队列的头元素，但是当元素不存在，remove抛出异常，poll则返回null。

法2：递归，当左右子节点都为空，返回true。

代码实现：

// bfs
public boolean isSymmetric(TreeNode root) {
    if (root == null || (root.left == null && root.right == null)) {
        return true;
    }
    Queue queue = new LinkedList();
    queue.add(root.left);
    queue.add(root.right);

    while (!queue.isEmpty()) {
        TreeNode left = queue.poll();
        TreeNode right = queue.poll();
        if (left == null && right == null) {
            continue;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        queue.add(left.left);
        queue.add(right.right);
        queue.add(left.right);
        queue.add(right.left);
    }
    return true;
}
// dfs
public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isSymmetric(root.left, root.right);
}

public boolean isSymmetric(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return true;
    if (t1 == null || t2 == null) return false;
    if (t1.val != t2.val) return false;
    return isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left);
}