讨论/《初级算法》 - 二叉树的层序遍历/
《初级算法》 - 二叉树的层序遍历
共 25 个回复

1,BFS解决

这题和剑指 Offer 32 - I. 从上到下打印二叉树其实是一样的,只不过上一题返回的是数组,这一题返回的是list。返回数组,我们还要初始化数组,但不知道数组的大小,所以一般是先储存在list中再转化为数组,返回list就比较简单了。
image.png

public List<List<Integer>> levelOrder(TreeNode root) {
    //边界条件判断
    if (root == null)
        return new ArrayList<>();
    //队列
    Queue<TreeNode> queue = new LinkedList<>();
    List<List<Integer>> res = new ArrayList<>();
    //根节点入队
    queue.add(root);
    //如果队列不为空就继续循环
    while (!queue.isEmpty()) {
        //BFS打印,levelNum表示的是每层的结点数
        int levelNum = queue.size();
        //subList存储的是每层的结点值
        List<Integer> subList = new ArrayList<>();
        for (int i = 0; i < levelNum; i++) {
            //出队
            TreeNode node = queue.poll();
            subList.add(node.val);
            //左右子节点如果不为空就加入到队列中
            if (node.left != null)
                queue.add(node.left);
            if (node.right != null)
                queue.add(node.right);
        }
        //把每层的结点值存储在res中,
        res.add(subList);
    }
    return res;
}

看下运行结果
image.png


2,DFS解决

这题让一层一层的打印,其实就是BFS,但使用DFS也是可以解决的,看一下

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    levelHelper(res, root, 0);
    return res;
}

public void levelHelper(List<List<Integer>> list, TreeNode root, int level) {
    //边界条件判断
    if (root == null)
        return;
    //level表示的是层数,如果level >= list.size(),说明到下一层了,所以
    //要先把下一层的list初始化,防止下面add的时候出现空指针异常
    if (level >= list.size()) {
        list.add(new ArrayList<>());
    }
    //level表示的是第几层,这里访问到第几层,我们就把数据加入到第几层
    list.get(level).add(root.val);
    //当前节点访问完之后,再使用递归的方式分别访问当前节点的左右子节点
    levelHelper(list, root.left, level + 1);
    levelHelper(list, root.right, level + 1);
}

看一下运行结果
image.png


我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

15

广度优先搜索

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> target;
        if(!root)
            return target;

        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            // 当前队列中的元素都是同一层的,n为该层元素数目
            int n = que.size();
            // 定义一个容器存储该层的节点的val值
            vector<int> tv;
            while(n--){
                TreeNode* tn = que.front(); que.pop();
                tv.push_back(tn->val);
                if(tn->left)
                    que.push(tn->left);
                if(tn->right)
                    que.push(tn->right);
            }
            target.push_back(tv);
        }
        return target;
    }
};
3

image.png

// Note: 该解法采用深度优先遍历二叉树,将结果存放到List<List<Integer>>中,其中外层list的index表示二叉树的层数,第二层list存放当前层的所有元素。如果 level == data.size() 则表示第一次遍历第 level 层,此时需要创建一个list存放第 level 层的元素。 当然,如果仅仅是广度优先遍历二叉树,可以使用一个队列来做缓存,但其无法知道第 level 层有哪些数据。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> data = new ArrayList<List<Integer>>();
        travel(data, root, 0);
        return data;
    }

    private void travel(List<List<Integer>> data, TreeNode root, int level) {
        if (root == null) {
            return;
        }
        // The first time to travel one layer, need to create a new list.
        if (level == data.size()) {
            data.add(new ArrayList<Integer>());
        }
        data.get(level).add(root.val);
        travel(data, root.left, level + 1);
        travel(data, root.right, level + 1);
    }
}
2

C语言队列自造轮子
4ms 11.3MB
喜欢的话点一个赞吧!

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

// Definition for singly-linked TreeNode list.
struct ListTreeNode {
    struct TreeNode *_node;
    struct ListTreeNode *next;
};

struct ListTreeNode *initiateListNode(struct TreeNode *tn) {
    struct ListTreeNode *tmp = malloc(sizeof(struct ListTreeNode));
    tmp->_node = tn;
    tmp->next = NULL;
    return tmp;
}

struct ListQueue {
    struct ListTreeNode *_front;
    struct ListTreeNode *_rear;
};

struct ListQueue *initiateQueue() {
    struct ListQueue *tmp = malloc(sizeof(struct ListQueue));
    tmp->_front = NULL;
    tmp->_rear = NULL;
    return tmp;
}

bool isEmptyQueue(struct ListQueue *q) {
    if (q->_front == NULL) return true;
    return false;
}

int countQueue(struct ListQueue *q) {
    int count = 0;
    for (struct ListTreeNode *tmp = q->_front; tmp != NULL; tmp = tmp->next) count++;
    return count;
}

struct ListTreeNode *pop(struct ListQueue *q) {
    if (isEmptyQueue(q)) return NULL;
    struct ListTreeNode *tmp = q->_front;
    q->_front = q->_front->next;
    if (q->_front == NULL) q->_rear = NULL;
    return tmp;
}

void push(struct ListQueue *q, struct ListTreeNode *ln) {
    if (isEmptyQueue(q)) {
        q->_front = ln;
        q->_rear = ln;
    } else {
        q->_rear->next = ln;
        q->_rear = q->_rear->next;
    }
}

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    struct ListQueue *queue = initiateQueue();
    struct ListTreeNode *node = initiateListNode(root);

    if (root != NULL) push(queue, node);

    int size = 0;
    int *columnSizes = malloc(sizeof(int) * size);
    int** res = malloc(sizeof(int*) * size);

    int i = 0;
    while (!isEmptyQueue(queue)) {
        size++;
        res = realloc(res, sizeof(int*) * size);
        columnSizes = realloc(columnSizes, sizeof(int) * size);
        columnSizes[i] = countQueue(queue);
        res[i] = malloc(sizeof(int) * (columnSizes[i]));
        int j = 0;

        // Initiate next_queue
        struct ListQueue *next_queue = initiateQueue();

        while (!isEmptyQueue(queue)) {
            struct TreeNode *tmp = pop(queue)->_node;
            res[i][j] = tmp->val;
            if (tmp->left != NULL) {
                node = initiateListNode(tmp->left);
                push(next_queue, node);
            }
            if (tmp->right != NULL) {
                node = initiateListNode(tmp->right);
                push(next_queue, node);
            }
            j++;
        }
        free(queue);
        queue = next_queue;
        i++;
    }
    free(queue);

    *returnColumnSizes = columnSizes;
    *returnSize = size;
    return res;
}
1

BFS

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
     if(root===null){
         return new Array();
     }
     let queue =new Array(); 
     let result=new Array();
     queue.push(root);
     while(queue.length>0){
         let item=new Array();
         let size=queue.length;
         for(let i=0;i<size;i++){
             let node=queue.shift();//获取第一个元素
             item.push(node.val);
             if(node.left!==null){
                 queue.push(node.left);
             }
             if(node.right!==null){
                 queue.push(node.right);
             }
         }
         result.push(item);
     }
     return result;
};
1
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(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 len = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < len; i++) {
                TreeNode item = queue.poll();
                list.add(item.val);
                if (item.left!=null) queue.add(item.left);
                if (item.right!=null) queue.add(item.right);
            }
            res.add(list);
        }
        return res;
    }
}

image.png

层序遍历

#include<queue>
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (root == nullptr) return {};
        vector<vector<int>> res;
        queue<TreeNode*> tree_queue;
        tree_queue.push(root);
        while(!tree_queue.empty()) {
            int size = tree_queue.size();
            vector<int> layer_val;
            while(size != 0) {
                TreeNode* node = tree_queue.front();
                tree_queue.pop();
                size--;
                if (node == nullptr) continue;
                layer_val.push_back(node->val);
                tree_queue.push(node->left);
                tree_queue.push(node->right);
            }
            if (layer_val.size() > 0) res.push_back(layer_val);
        }
        return res;
    }
};

image.png

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) {
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            List<Integer> child = new ArrayList<>();
            int len = queue.size();
            for(int i = 0; i < len; i++) {
                TreeNode temp = queue.poll();
                child.add(temp.val);
                if(temp.left != null) {
                    queue.offer(temp.left);
                }
                if(temp.right != null) {
                    queue.offer(temp.right);
                }
            }
            
            res.add(child);
        }
        return res;
    }
}

image.png

javascript DFS

var levelOrder = function (root) {
  let res = [];
  const dfs = (root, level) => {
    if (!root) return;
    res[level] ? res[level].push(root.val) : (res[level] = [root.val]);
    dfs(root.left, level + 1);
    dfs(root.right, level + 1);
  };
  dfs(root, 0);
  return res;
};
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        all_list = []
        node_list = [root]
        while node_list:
            lens = len(node_list)
            new = []
            for i in range(lens):
                node = node_list.pop(0)
                new.append(node.val)
                if node.left:
                    node_list.append(node.left)
                if node.right:
                    node_list.append(node.right)
            if new:
                all_list.append(new)
        return all_list