【作业11】二叉树层序遍历（变形版）-跟着帅地玩副业，开拓第二曲线PlayOffer

幽小皮永久会员 2024年5月7日下午9:23

“
//打卡
public List<List> decorateRecord(TreeNode root) {
if(root null){
return new ArrayList();
}

    Queue<TreeNode> queue = new LinkedList<>();
    List<List<Integer>> res = new ArrayList<>();
    int r = 1;

    queue.add(root);
    while(!queue.isEmpty()){
        int size = queue.size();
        List<Integer> t = new LinkedList<>();
        for(int i = 0; i < size; i++){
            TreeNode temp = queue.poll();
            if(r % 2 == 1){
                t.add(temp.val);
            }else{
                t.addFirst(temp.val);
            }
            if(temp.left != null){
                queue.add(temp.left);
            }
            if(temp.right != null){
                queue.add(temp.right);
            }



        }
        r++;
        res.add(t);
    }
    return res;
}

“java

0 赞同 0 条回复

开心果🍅 永久会员 2024年4月9日下午10:03

打卡

“`java
/**
* 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 {
Queue queue = new LinkedList<>();
List> res = new ArrayList<>();
public List> decorateRecord(TreeNode root) {
if(root == null) return new ArrayList>();
queue.add(root);
int count =0;
while(!queue.isEmpty() && root != null){
count++;
List t = new ArrayList<>();
int size = queue.size();
for(int i = 0; i< size; i++){ TreeNode temp = queue.poll(); if(count%2==1){ t.add(temp.val); } if(count%2==0){ t.add(0,temp.val); }

              if(temp.left != null){
                     queue.add(temp.left);
              }
              if(temp.right != null){
                     queue.add(temp.right);
               }
        }
        res.add(t);

    }

    return res;
}

}

0 赞同 0 条回复

Mr.肖永久会员 2024年4月9日下午5:29

/**
 * 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>> decorateRecord(TreeNode root) {
        List<List<Integer>> list = new LinkedList<>();
        if(root == null){
            return list;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        //标志位：是否从头部插入
        boolean flag = false;
        queue.offer(root);

        while(!queue.isEmpty()){
            int n = queue.size();
            List<Integer> t = new LinkedList<>();

            for(int i=0; i < n; i++){
                TreeNode temp = queue.poll();
                if(flag){
                    t.add(0,temp.val);
                }else{
                    t.add(temp.val);
                }
                if(temp.left != null){
                    queue.offer(temp.left);
                }
                if(temp.right != null){
                    queue.offer(temp.right);
                }
            }
            flag = !flag;
            list.add(t);

        }

        return list;
    }
}

0 赞同 0 条回复

𬍤永久会员 2023年11月12日上午10:51

打卡

class Solution {
    public List<List<Integer>> decorateRecord(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }

        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        int sum = 1;
        queue.add(root);
        while(!queue.isEmpty()){
            int k = queue.size();
            LinkedList<Integer> temp = new LinkedList<>();
            for(int i = 0; i < k; i++){
                TreeNode t = queue.poll();
                if(sum % 2 == 1){
                    temp.add(t.val);
                }else{
                    temp.addFirst(t.val);//
                }

                if(t.left != null)  queue.add(t.left);
                if(t.right != null)  queue.add(t.right);
            }
            res.add(temp);
            sum++;
        }
        return res;
    }
}

0 赞同 0 条回复

Thaddeus 永久会员 2023年10月10日下午2:31

打卡

class Solution {
public:
    vector<vector<int>> decorateRecord(TreeNode* root) {
        if(root == nullptr) return {};

        vector<vector<int>> res;
        queue<TreeNode*> que;
        que.push(root);
        int cnt = 0;
        while(!que.empty()) {
            int _size = que.size();
            vector<int> path;
            while(_size--) {
                TreeNode* node = que.front();
                que.pop();
                path.push_back(node->val);
                if(node->left != nullptr) que.push(node->left);
                if(node->right != nullptr) que.push(node->right);
            }
            if(cnt % 2 == 1) reverse(path.begin(), path.end());
            res.push_back(path);
            cnt++;
        }
        return res;
    }
};

0 赞同 0 条回复

泡芙永久会员 2023年9月21日下午2:30

class Solution {
    public List<List<Integer>> decorateRecord(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new LinkedList<>();

        int sum = 1;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            LinkedList<Integer> level = new LinkedList<>();
            for (int i = 0; i < size; i ++) {
                TreeNode temp = queue.poll();
                // 奇数行从左到右打印
                if (sum % 2 == 1) {
                    level.add(temp.val);
                } else {
                    // 偶数行从右到左打印
                    level.addFirst(temp.val);
                }

                if (temp.left != null) {
                    queue.offer(temp.left);
                }
                if (temp.right != null) {
                    queue.offer(temp.right);
                }
            }
            res.add(level);
            sum ++;
        }
        return res;
    }
}

0 赞同 0 条回复

八点上线永久会员 2023年9月13日上午11:12

/**
 * 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 LinkedList();
        Queue<TreeNode> queue = new LinkedList();
        if(root == null){
            return res;
        }

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

    }
}

打卡

0 赞同 0 条回复

阿尚普通 2023年8月21日上午10:34

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null) return list;

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int layerSize = queue.size();
            LinkedList<Integer> layerlist = new LinkedList<>();//双端队列
            for(int i = 0; i < layerSize; i++){
                    TreeNode node = queue.poll();
                    //根据list当前的层数来判断从队头入队还是队尾入队
                    if(list.size() % 2 == 0){
                        layerlist.addLast(node.val);
                    }else{
                        layerlist.addFirst(node.val);
                    }

                    if(node.left != null) queue.offer(node.left);
                    if(node.right != null) queue.offer(node.right);
            }
            list.add(layerlist);
        }

        return list;
    }
}

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月8日下午4:32

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        List<List<Integer>> ans = new LinkedList<>();
        if(root == null) {
            return ans;
        }

        int f = -1;  //-1代表奇数层，1代表偶数层
        q.offer(root);
        while(!q.isEmpty()) {
            int cnt = q.size();
            List<Integer> res = new LinkedList<>();
            for(int i = 0; i < cnt; i++) {
                TreeNode temp = q.poll();
                if(temp.left != null) {
                    q.offer(temp.left);
                }
                if(temp.right != null) {
                    q.offer(temp.right);
                }
                if(f == -1)
                    res.add(temp.val);
                else
                    res.add(0, temp.val);
            }
            f *= -1;
            ans.add(res);
        }

        return ans;
    }
}

0 赞同 0 条回复

小肸永久会员 2023年6月11日下午11:08

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        int height = 0;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int count = queue.size();
            List<Integer> temp = new ArrayList<>();
            for (int i = 0; i < count; i ++) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            height ++;
            if (height % 2 == 0) {
                Collections.reverse(temp);
            }
            res.add(new ArrayList<>(temp));
        }
        return res;

    }
}

弄清那一层需要反转。

0 赞同 0 条回复

upward ᯤ⁶⁰ᴳ 永久会员 2023年6月6日上午9:39

class Solution {
public List<List> levelOrder(TreeNode root) {
Queue que=new ArrayDeque<>();
List<List> res = new ArrayList<>(1);
if(rootnull)
return res;
res.add(new ArrayList(1));
que.offer(root);
boolean flag=false;
int levelLen=1;
int idx=0;
while(!que.isEmpty()){
TreeNode cur= que.poll();
res.get(idx).add(cur.val);
if(cur.left!=null)
que.offer(cur.left);
if(cur.right!=null)
que.offer(cur.right);
levelLen–;
if(levelLen0){
levelLen=que.size();
if(flag){
Collections.reverse(res.get(idx));
}
flag=!flag;
idx++;
res.add(new ArrayList(levelLen));
}
}
res.remove(idx);
return res;
}
}//时间O(n) 空间O(n)

0 赞同 0 条回复

菜心永久会员 2023年5月20日下午9:29

“`java
class Solution {
public List> levelOrder(TreeNode root) {
if(root == null){
return new ArrayList<>();
}

    Queue queue = new LinkedList();
    List> res = new ArrayList();
    int count = 0;
    queue.add(root);
    while(!queue.isEmpty()){

        int size = queue.size();
        count++;
        List t = new ArrayList<>();
        for(int i = 0; i < size; i++){
            TreeNode temp = queue.poll();

            if(count % 2 == 0){
                t.add(0, temp.val);
            }else{
                t.add(temp.val);
            }

            if(temp.left != null){
                queue.add(temp.left);
            }
            if(temp.right != null){
                queue.add(temp.right);
            }
        }
        res.add(t);

    }
    return res;
}

}//时间O(n) 空间O(n)

0 赞同 0 条回复

是梦终空永久会员 2023年5月20日上午11:20

时间O(n)
空间O(n)

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> que = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root == null)    return res;
        que.add(root);
        int k =1;       //标记位
        while(!que.isEmpty()){
            int len = que.size();
            LinkedList<Integer> list = new LinkedList<>();
            //遍历队列 
            for(int i = 0;i<len;i++){
                TreeNode pre = que.poll();
                if(k%2 == 1){           //右到左遍历
                    list.add(pre.val);    
                }else{                  //左到右遍历
                    list.addFirst(pre.val);     //添加到链表头部
                }
                if(pre.left!=null)     que.add(pre.left);
                if(pre.right!=null)    que.add(pre.right);

            }
            res.add(list);
            k++;
        }
        return res;
    }
}

0 赞同 0 条回复

毛头小子永久会员 2023年5月17日下午4:08

    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);
        boolean a = true;
        while(!queue.isEmpty()){
            int n = queue.size();
            List<Integer> list = new ArrayList<>();
            for(int i = 0 ; i < n ; i++){
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null){
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                }
            }
            if(a == false){//反转要放到list加完一层以后
                Collections.reverse(list);
            }
            a = a == true ? false:true;
            res.add(list);
        }
        return res;
    }

0 赞同 0 条回复

庄重普通 2023年5月15日下午7:49

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {

        if(root == NULL) return {};

        queue<TreeNode*> Queue;
        vector<vector<int>> Ret;
        int flag = 1;
        Queue.push(root);

        while(!Queue.empty()) {

            int size = Queue.size();
            vector<int> vTmp;
            int i = 0;
            for(i = 0; i < size; i ++) {

                TreeNode *pTmp = Queue.front(); Queue.pop();
                vTmp.push_back(pTmp->val);
                if(pTmp->left != NULL) Queue.push(pTmp->left);
                if(pTmp->right != NULL) Queue.push(pTmp->right);
            }
            if((flag & 1) == 0) {
                reverse(vTmp.begin(), vTmp.end());
            }
            flag ++;
            Ret.push_back(vTmp);
        }
        return Ret;
    }
};
// 时间复杂度O(n);
// 空间复杂度O(n);

0 赞同 0 条回复

Everglow 永久会员 2023年5月15日下午3:05

时间O（n）空间O（n）

class Solution {
    public List> levelOrder(TreeNode root) {
        List> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Deque queue = new LinkedList<>();
        queue.offer(root);
        boolean b = false;
        while (!queue.isEmpty()) {
            LinkedList list = new LinkedList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (b) {
                    list.addFirst(node.val);
                } else {
                    list.addLast(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            b = b == true ? false : true;
            res.add(list);
        }
        return res;
    }
}

1 赞同 0 条回复

【作业11】二叉树层序遍历（变形版）

参考答案

共以下 16 个回答

# 回答此问题取消回复

【作业11】二叉树层序遍历（变形版）

参考答案

共以下 16 个回答

# 回答此问题 取消回复

# 回答此问题取消回复