LeetCode ---- 102. 二叉树的层次遍历 ( java, c++)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode ---- 102. 二叉树的层次遍历 ( java, c++)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1832字，纯文字阅读大概需要3分钟。

内容图文

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList();
        if(root == null){
            return res;
        }
       
        Queue<TreeNode> q = new LinkedList();//层次遍历，用队列实现
        q.offer(root); //将根节点入队
        TreeNode last = root; //last指向当前操作层的最后一个节点
        TreeNode nlast = root; //nlast指向下一层的最后一个节点
        TreeNode t = null;
        List<Integer> list = new ArrayList();
        
        while(!q.isEmpty()){
            t = q.poll(); //出队并返回出队节点
            list.add(t.val); //加入节点值
            
            if(t.left != null){
                q.offer(t.left);
                nlast = t.left;
            }
            if(t.right != null){
                q.offer(t.right);
                nlast = t.right;
            }
            
            if(t == last){ //遇到这层的最后一个节点
                last = nlast; //换行
                res.add(list);
                list = new ArrayList(); //重新开辟一个新的list存下一层节点数
            }
        }
        
        return res;
    }
}

 

C++:

二叉树层序遍历有两种方法，分别是深度优先和广度优先：

深度优先（DFS）实现：

void traversal(TreeNode *root, int level, vector<vector<int>> &result) {
    if (!root) {
        return;
    }
    // 保证每一层只有一个vector
    if (level > result.size()) {
        result.push_back(vector<int>());
    }
    result[level-1].push_back(root->val);
    traversal(root->left, level+1, result);
    traversal(root->right, level+1, result);
}

vector<vector<int> > levelOrder(TreeNode *root) {
    vector<vector<int>> result;
    traversal(root, 1, result);
    return result;
}

广度优先（BFS）实现：

vector<vector<int>> levelOrder(TreeNode* root) {
    std:queue<TreeNode *> q;
    TreeNode *p;

    vector<vector<int>> result;
    if (root == NULL) return result;

    q.push(root);

    while (!q.empty()) {
        int size = q.size();
        vector<int> levelResult;

        for (int i = 0; i < size; i++) {
            p = q.front();
            q.pop();

            levelResult.push_back(p->val);

            if (p->left) {
                q.push(p->left);
            }
            if (p->right) {
                q.push(p->right);
            }
        }

        result.push_back(levelResult);
    }

    return result;
}

 

 

 

内容总结

以上是互联网集市为您收集整理的LeetCode ---- 102. 二叉树的层次遍历 ( java, c++)全部内容，希望文章能够帮你解决LeetCode ---- 102. 二叉树的层次遍历 ( java, c++)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---