YOLO 普通 2024年3月28日下午2:39

 /*之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，
 第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印， */
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<>();

        queue.add(root);

        int sum = 1;
        while(!queue.isEmpty()){
            int k = queue.size();
            List<Integer> arr = new ArrayList<>();

            for(int i=0;i<k;i++){
                TreeNode t = queue.poll();
                if(sum % 2 == 1){   //判断奇偶行，奇数行直接加，偶数行First加
                    arr.add(t.val);
                }
                else{
                    arr.addFirst(t.val);
                }           
                if(t.left != null){
                    queue.add(t.left);
                }
                if(t.right != null){
                    queue.add(t.right);
                }
            }     
            sum++;
            res.add(arr);    
        } 
        return res;
    }   
}

0 赞同 0 条回复

NULL 普通 2024年3月20日下午9:03

/**
* 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> decorateRecord(TreeNode root) {
if(root null)return new ArrayList<>();

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

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

}时

0 赞同 0 条回复

kfaebot 普通 2024年3月15日上午10:11

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> decorateRecord(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> que;

        if(root!=nullptr){
            que.push(root);
        }
        int flag=1;
        while(!que.empty()){
            int size=que.size();
            vector<int>vec;

            for(int i=0;i<size;i++){
                TreeNode* tmp=que.front();
                que.pop();
                vec.push_back(tmp->val);

                if(tmp->left!=nullptr){
                    que.push(tmp->left);
                }
                if(tmp->right!=nullptr){
                    que.push(tmp->right);
                }
            }
            if(flag%2==0){
                reverse(vec.begin(),vec.end());
            }
            flag++;
            result.push_back(vec);
        }
        return result;
    }
};
//比正常的层序遍历多了一步判断奇数偶数层
//时间和空间复杂度均为O(N)

0 赞同 0 条回复

Let it be 永久会员 2024年3月12日下午10:40

class Solution {
public List<List> decorateRecord(TreeNode root) {
List<List> res = new ArrayList();
Queue queue = new LinkedList();
if(root != null ) queue.add(root);
while(!queue.isEmpty()){
LinkedList tmp = new LinkedList();
for(int i = queue.size();i >0;i–){
TreeNode node = queue.poll();
if(res.size()%2 0){
tmp.addLast(node.val);
}else{tmp.addFirst(node.val);}
if(node.left != null)queue.add(node.left);
if(node.right != null)queue.add(node.right);
}
res.add(tmp);
}
return res;
}
}时间空间复杂度O（n）

0 赞同 0 条回复

东普通 2024年3月12日下午8:39

~~~java
class Solution {
public List<List> decorateRecord(TreeNode root) {
if(rootnull) {
return new ArrayList<List>();
}

    List<List<Integer>> res = new ArrayList<List<Integer>>();
    LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    //将根节点放入队列中，然后不断遍历队列
    queue.add(root);
    int level = 1;
    while(queue.size()>0) {
        //获取当前队列的长度，这个长度相当于 当前这一层的节点个数
        int size = queue.size();
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        //将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中
        //如果节点的左/右子树不为空，也放入队列中
        for(int i=0;i<size;++i) {
            TreeNode t = queue.remove();
            tmp.add(t.val);
            if(t.left!=null) {
                queue.add(t.left);
            }
            if(t.right!=null) {
                queue.add(t.right);
            }
        }
        //如果是偶数层就将列表反转
        if(level % 2 == 0){
            Collections.reverse(tmp);
        }
        //将临时list加入最终返回结果中
        res.add(tmp);
        level++;
    }
    return res;
}

}
java

0 赞同 0 条回复

　南木普通 2024年3月12日下午8:08

根据上一题加个栈进行判定

/**
 * 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) {
        if(root == null){
            return new ArrayList<>();
        }

        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        int j = 0;
        queue.add(root);
        while(!queue.isEmpty()){
            int k = queue.size();
            List<Integer> tmp1 = new ArrayList<>();
            List<Integer> tmp2 = new ArrayList<>();
            Stack<Integer> s = new Stack<>();
            for(int i = 0; i < k; i++){
                TreeNode t = queue.poll();
                tmp1.add(t.val);
                if(j % 2 == 1){
                    s.push(t.val);
                }
                if(t.left != null) queue.add(t.left);
                if(t.right != null) queue.add(t.right);
            }
            if(j % 2 == 1){
                while(!s.isEmpty()){
                    tmp2.add(s.pop());
                }
                res.add(tmp2);
            }else{
                res.add(tmp1);
            }
            j++;
        }
        return res;
    }
}

0 赞同 0 条回复

ChenZhangHangTime 永久会员 2024年3月12日下午6:22

这题其实说难不难，说简单也不算简单，我觉得关键的地方在于你有没有做过前两道题，如果你做过前两道题，那么这题基本就是白给，很快就做出来了，就是多加了一个sum去判断奇偶层，因为奇层和偶层的逻辑不一样。但如果没做过前两道题，那这题基本上是做不出来的，我也是昨天把前两道题看了一下，然后今天再复习一遍，才做的这道题。不过做的时候也磕磕绊绊，要多次看一下答案才能勉强做出来。
public List<List> levelOrder(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> tmp = new LinkedList<>();
        for(int i = 0; i < k; i++){
            TreeNode t = queue.poll();
            if(sum % 2 = = 1){
                tmp.add(t.val);
            } else {
                tmp.addFirst(t.val);
            }

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

    return res;
}

0 赞同 0 条回复

一个达不刘普通 2024年3月12日下午3:43

class Solution {
public:
vector<vector> decorateRecord(TreeNode* root) {
vector<vector> arr;
queue que;
if(root != nullptr) que.push(root);

    int count =0;
    while(!que.empty()){
        count++;
        vector<int> tmp;//设置临时一维数组
        for(int i=que.size();i>0;i--){//循环每层的元素个数
            root = que.front();//队头出队
            que.pop();
            tmp.push_back(root->val);//插入临时数组
            if(root->left) que.push(root->left);
            if(root->right) que.push(root->right);
        }
        if(count % 2 ==0){
            reverse(tmp.begin(),tmp.end());//偶数层，倒序
        }
        arr.push_back(tmp);

    }
    return  arr;   
}

};

0 赞同 0 条回复

RunAsOne 普通 2024年3月12日下午3:19

第n次打卡如履薄冰

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def decorateRecord(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[List[int]]
        """
        if not root:
            return []
        res = []
        queue = collections.deque()
        queue.append(root)
        count = 0
        while queue:
            r = []
            count+=1
            for _ in range(len(queue)):
                tmp = queue.popleft()
                if count % 2 == 0:
                    r.insert(0, tmp.val)
                else:
                    r.append(tmp.val)
                if tmp.left:
                    queue.append(tmp.left)
                if tmp.right:
                    queue.append(tmp.right)
            res.append(r)
        return res

0 赞同 0 条回复

MARS 普通 2024年3月11日下午11:01

day8第三题

function decorateRecord(root: TreeNode | null): number[] {
    if (root == null) return []
    let queue = [root], num = 1  //用队列，num计算现在一层多少个节点
    let res = [], change = 0
    while (queue.length > 0) {
        let count = 0
        let level = []
        while (num != 0) {  //将该层全部元素全部拿出
            let node = queue.shift()
            if (change % 2 == 0) {
                level.push(node.val)
            } else {
                level.unshift(node.val)
            }
            if (node.left) {
                queue.push(node.left)
                count++
            }
            if (node.right) {
                queue.push(node?.right)
                count++
            }
            num--
        }
        num = count  //将下一层数目给到num
        res.push(level)
        change++
    }
    return res
};

0 赞同 0 条回复

叫不醒装睡的人普通 2024年3月11日下午9:45

class Solution {
    // 解法跟之前的题目一致
    // 用一个标记变量记录每一层的顺逆序
    public List<List<Integer>> decorateRecord(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        List<List<Integer>> result = new LinkedList<>();
        boolean flag = true;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> tempList = new LinkedList<>();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (flag) {
                    tempList.add(node.val);
                } else {
                    tempList.addFirst(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            result.add(tempList);
            flag = !flag;
        }
        return result;
    }
    // 时间复杂度为 O(n)
    // 空间复杂度为 O(n)
}

0 赞同 0 条回复

言之命至普通 2024年3月11日下午9:22

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<>();
        int sum = 1;
        queue.add(root);
        while(!queue.isEmpty()){
            int k = queue.size();
            LinkedList<Integer> tmp = new LinkedList<>();
            for(int i = 0; i < k; i++){
                TreeNode t = queue.poll();
                if(sum % 2 = = 1){
                    tmp.add(t.val);
                } else { //偶数行，从前面插
                    tmp.addFirst(t.val);
                }

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

        return res;
    }
}
//双端队列实现左右顺序互换，用res的奇偶层数确定遍历的方向

0 赞同 0 条回复

Free 普通 2024年3月11日下午8:06

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution 
{
public:
    vector<vector<int>> decorateRecord(TreeNode* root) 
    {
        vector<vector<int>> res;
        if(root == nullptr)
            return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            int qsize = q.size();
            vector<int> path;
            for(int i = 0; i < qsize; i++)
            {
                TreeNode* front = q.front();
                q.pop();
                path.push_back(front->val);
                if(front->left)
                    q.push(front->left);
                if(front->right)
                    q.push(front->right);
            }
            res.push_back(path);
            path.clear();
        }
        for(int i = 0; i < res.size(); i++)
            if(i % 2)
                reverse(res[i].begin(), res[i].end());
        return res;
    }
};

时空复杂度O(n)

0 赞同 0 条回复

helloMoon 普通 2024年3月11日下午3:30

剑指 Offer 32 – III. 从上到下打印二叉树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 {
    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> tmp = new LinkedList<>();
            for(int i = 0; i < k; i ++ ){
                TreeNode t = queue.poll();
                if(sum % 2  == 1){
                    tmp.add(t.val);
                }else{
                    tmp.addFirst(t.val);
                }

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

0 赞同 0 条回复

mpweixin用户普通 2024年3月11日下午2:39

public List<List> decorateRecord(TreeNode root) {
Queue q=new LinkedList<>();
List<List> res =new ArrayList<>();
if(root null) return res;
q.add(root);
while(!q.isEmpty()){
Listtmp =new ArrayList<>();
for(int i=q.size();i>0;i–){
TreeNode node = q.poll();
if(res.size() % 2 0) tmp.addLast(node.val);
else tmp.addFirst(node.val);
if(node.left != null) q.add(node.left);
if(node.right != null) q.add(node.right);
}
res.add(tmp);
}
return res;
}
思路:双端队列实现左右顺序互换，用res的奇偶层数确定遍历的方向

0 赞同 0 条回复

南梁陈庆之普通 2024年3月11日上午11:37

广度优先算法，注意下每层转换下输出顺序，使用一个布尔值判断
时间复杂度O（N）
空间复杂度O（N）

/**
 * 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 ArrayList<>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean flg = true;
        while (!queue.isEmpty()) {
            int n = queue.size();
            List<Integer> tempList = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                tempList.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }

            if (flg) {
                list.add(tempList);
            } else {
                List<Integer> reverList = new ArrayList<>();    
                for (int i = tempList.size() - 1; i >= 0 ;i--) {
                    reverList.add(tempList.get(i));
                }
                list.add(reverList);
            }
            flg = !flg;

        }
        return list;
    }
}

0 赞同 0 条回复

神经蛙普通 2024年3月11日上午12:13

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

    queue<TreeNode*> q{{root}};
    vector<vector<int>> res;
    int sum = 1;
    while (!q.empty()) {
        int n = q.size();
        vector<int> level(n);
        for (int i = 0; i < n; ++i) {
            auto t = q.front();
            q.pop();
            if (sum % 2 == 1) {
                level[i] = t->val;
            } else {
                level[n - 1 - i] = t->val;
            }
            if (t->left)  q.push(t->left);
            if (t->right) q.push(t->right);
        }
        res.push_back(level);
        ++sum;
    }
    return res;
}

};
打卡，和前面一题的主要区别是记录一层节点的顺序

0 赞同 0 条回复

mpweixin用户普通 2024年3月10日下午9:59

java
class Solution {
public List<List> decorateRecord(TreeNode root) {
Queue queue = new LinkedList<>();
List<List> res = new ArrayList<>();
if(root != null) queue.add(root);
while(!queue.isEmpty()){
LinkedList tmp = new LinkedList<>();
for(int i = queue.size(); i > 0; i–){
TreeNode node = queue.poll();
if(res.size() % 2 0) tmp.addLast(node.val);
else tmp.addFirst(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
res.add(tmp);
}
return res;
}
}
时间复杂度 O(N)
空间复杂度 O(N)

0 赞同 0 条回复

方铎码农普通 2024年3月10日下午5:43

class Solution {
    public List<List<Integer>> decorateRecord(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()){
            //Java中使用双端队列（Deque或者LinkedList）可以实现分层换向
            LinkedList<Integer> tmp = new LinkedList<>();
            for(int i = queue.size(); i > 0; i--){
                TreeNode node = queue.poll();
                if(res.size() % 2 == 0){
                    tmp.addLast(node.val);
                } else {
                    tmp.addFirst(node.val);
                }

                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

时间复杂度$O(n)$，额外空间复杂度$O(n)$，将第二题的分层子队列改成可以按照层数换向的双端队列即可（由于返回值是List类，需要用List类的实现LinkedList）

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月10日下午4:51

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

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

        queue.add(root);
        while(!queue.isEmpty()){
            int k = queue.size();
            List<Integer> tmp = new ArrayList<>();
            for(int i = 0; i < k; i++){
                TreeNode t = queue.poll();

                if(sum%2==1) tmp.add(t.val);
                else tmp.addFirst(t.val);

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

        return res;
    }
}

时间复杂度：O(n)
额外空间复杂度：容器里最对存放 1/2 的节点，故为 O(n)

0 赞同 0 条回复

Jimmy 普通 2024年3月10日下午4:17

时间复杂度O(n)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> decorateRecord(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> que;
        int level = 0;
        if(root)que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> tmpAns(size);
            level++;//用来记录是第几层
            int end = size;//倒着放数值的索引
            for(int i=0;i<size;i++){//用来遍历某层

                TreeNode *cur = que.front();
                que.pop();
                if(level%2 == 1){//奇数层将数值正放
                    tmpAns[i] = cur->val;
                }else{//偶数层将数值倒放
                    tmpAns[--end] = cur->val;
                }
                if(cur->left)que.push(cur->left);
                if(cur->right)que.push(cur->right);

            }
            ans.push_back(tmpAns);
        }
        return ans;
    }
};

0 赞同 0 条回复

Yuki 永久会员 2024年3月10日上午10:53

层序遍历变形

class Solution {
public:
vector<vector> decorateRecord(TreeNode* root) {
vector<vector>res;
queue<TreeNode*>que;
if(rootnullptr)return res;
que.push(root);
int flag=0;

    while(!que.empty()){
        int size=que.size();
        vector<int>vec;
        flag++;

        for(int i=0;i<size;i++){

            TreeNode*tmp=que.front();
            vec.push_back(tmp->val);
            que.pop();

            if(tmp->left)que.push(tmp->left);
            if(tmp->right)que.push(tmp->right);
        }

        if(flag%2==0){
            reverse(vec.begin(),vec.end());
        }

        res.push_back(vec);
    }
    return res;
}

};

//时间复杂度：O(N)

0 赞同 0 条回复

进取普通 2024年3月10日上午10:25

class Solution {
public:
vector<vector> decorateRecord(TreeNode* root) {
vector<vector> ret;
if (root nullptr) return ret;
deque<TreeNode> de;
de.push_back(root);
int num = 1;
while (!de.empty()){
vector tmp;
if (num % 2 1){//奇数
for (int i = de.size(); i > 0; –i){
TreeNode node = de.front();
de.pop_front();
tmp.push_back(node->val);
if (node->left) de.push_back(node->left);
if (node->right) de.push_back(node->right);

            }
        }
        if (num % 2 == 0){//偶数
            for (int i = de.size(); i > 0; --i){
                TreeNode* node = de.back();
                de.pop_back();
                tmp.push_back(node->val);
                if (node->right) de.push_front(node->right);
                if (node->left) de.push_front(node->left);  
            }   
        }
        ret.push_back(tmp);
        ++num;    
    }
    return ret; 
}

};双端队列控制奇偶打印时空复杂度O(N)

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月10日上午9:38

打卡

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

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

0 赞同 0 条回复

Yox 普通 2024年3月10日上午5:44

Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

class Solution:
def decorateRecord(self, root: TreeNode) -> List[List[int]]:
if not root: return []
res, deque = [], collections.deque()
deque.append(root)
while deque:
tmp = []
# 打印奇数层
for _ in range(len(deque)):
# 从左向右打印
node = deque.popleft()
tmp.append(node.val)
# 先左后右加入下层节点
if node.left: deque.append(node.left)
if node.right: deque.append(node.right)
res.append(tmp)
if not deque: break # 若为空则提前跳出
# 打印偶数层
tmp = []
for _ in range(len(deque)):
# 从右向左打印
node = deque.pop()
tmp.append(node.val)
# 先右后左加入下层节点
if node.right: deque.appendleft(node.right)
if node.left: deque.appendleft(node.left)
res.append(tmp)
return res

双 o n

0 赞同 0 条回复

Raphtalia. 普通 2024年3月10日上午12:53

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
#include
class Solution {
public:
vector<vector> decorateRecord(TreeNode root) {
deque<TreeNode> q;
vector<vector> ans;
if(root != nullptr) q.push_back(root);
while(!q.empty()){
vector tmp;
for(int i = q.size(); i > 0; i –){
TreeNode cur = q.front();
q.pop_front();
tmp.push_back(cur->val);
if(cur->left != nullptr) q.push_back(cur->left);
if(cur->right != nullptr) q.push_back(cur->right);
}
ans.push_back(tmp);
if(q.empty()) break;
tmp.clear();
for(int i = q.size(); i > 0; i –){
TreeNode* cur = q.back();
q.pop_back();
tmp.push_back(cur->val);
if(cur->right != nullptr) q.push_front(cur->right);
if(cur->left != nullptr) q.push_front(cur->left);
}
ans.push_back(tmp);
}
return ans;
}
};
时空复杂度O（n）

0 赞同 0 条回复

heathhou 普通 2024年3月9日下午10:45

class Solution {
public:
    vector<vector<int>> decorateRecord(TreeNode* root) {
        vector<vector<int>> result;
        if(root == nullptr)
            return result;
        queue<TreeNode*> q;
        q.push(root);
        int num = 1;
        while(!q.empty()){
            int n = q.size();
            vector<int> v(n);
            for(int i = 0; i < n; ++i){
                auto t = q.front();
                q.pop();
                // 第奇数层
                if(num == 1){
                    v[i] = t->val;
                }
                // 第偶数层
                else{
                    v[n - i - 1] = t->val;
                }


                if(t->left)
                    q.push(t->left);
                if(t->right)
                    q.push(t->right);

            }
            result.push_back(v);
            num = num * -1;
        }

        return result;
    }
};

0 赞同 0 条回复

云无深雁影普通 2024年3月9日下午10:33

class Solution {
public List<List> decorateRecord(TreeNode root) {
List<List> ans = new ArrayList<>();
if(root null) return ans;
Stack stack1 = new Stack<>();
Stack stack2 = new Stack<>();
stack1.add(root);
while(!stack1.isEmpty()){
List layer = new ArrayList<>();
int len = stack1.size();
for(int i = 0; i < len; i++){
TreeNode temp = stack1.pop();
layer.add(temp.val);
if(temp.left!=null) stack2.push(temp.left);
if(temp.right!=null) stack2.push(temp.right);
}
ans.add(layer);
List layer2 = new ArrayList<>();
if(stack2.isEmpty())
break;
len = stack2.size();
for(int i = 0; i < len; i++){
TreeNode temp = stack2.pop();
layer2.add(temp.val);
if(temp.right!=null) stack1.push(temp.right);
if(temp.left!=null) stack1.push(temp.left);
}
ans.add(layer2);
}
return ans;

}
//使用两个栈实现

0 赞同 0 条回复

机电皮怪永久会员 2024年3月9日下午9:59

时间复杂度O(n)
空间复杂度O(n)

“`C++
class Solution {
public:
vector> decorateRecord(TreeNode* root)
{
if(root == nullptr)
{
return {};
}

    queue<TreeNode*> sub;
    sub.push(root);
    vector<vector<int>> result;
    int count = 0;
    while(sub.empty() == false)
    {
        vector<int> tmp;
        for(int i = 0, j = sub.size(); i < j; i++)
        {
            TreeNode* temp = sub.front();
            sub.pop();
            tmp.push_back(temp->val);
            if(temp->left != nullptr)
            {
                sub.push(temp->left);
            }
            if(temp->right != nullptr)
            {
                sub.push(temp->right);
            }
        }
        if(count % 2 == 1)
        {
            reverse(tmp.begin(), tmp.end());
        }
        result.push_back(tmp);
        count++;
    }

    return result;
}

};

“`

0 赞同 0 条回复

莫～慢～待普通 2024年3月9日下午8:31

class Solution {
public List<List> decorateRecord(TreeNode root) {
List<List> res=new ArrayList<>();
if(rootnull)
{
return res;
}
Queue queue=new LinkedList<>();
queue.offer(root);
int count=queue.size();
boolean flag=true;
while(!queue.isEmpty())
{
List list_res=new ArrayList<>();
for(int i=0;i<count;i++)
{
TreeNode node=queue.poll();
list_res.add(node.val);
if(node.left!=null)
queue.offer(node.left);
if(node.right!=null)
queue.offer(node.right);
}
count=queue.size();
if(!flag)
{
Collections.reverse(list_res);
flag=true;
}
else
flag=false;
res.add(list_res);
}
return res;
}
}
维护一个布尔变量，决定当前层的list是否反转顺序

0 赞同 0 条回复

王位詮釋普通 2024年3月9日下午7:45

class Solution {
    public List<List<Integer>> decorateRecord(TreeNode root) {
        List<List<Integer>> results = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if(root!=null){
            deque.offer(root);
        }
        boolean flag = false;
        while(!deque.isEmpty()){
            List<Integer> result = new ArrayList<>();
            for(int i=deque.size();i>0;i--){
                TreeNode temp = deque.poll();
                result.add(temp.val);
                if(temp.left!=null){
                    deque.offer(temp.left);
                }
                if(temp.right!=null){
                    deque.offer(temp.right);
                }
            }
            if(flag){
                Collections.reverse(result);
                results.add(result);
            }else{
                results.add(result);
            }
            flag = !flag;
        }
        return results;
    }
}
思路：大致思路是和前一道题是一样的，只是加了反转
设置一个反转位，如果需要反转的时候就进行反转，否则就按照正常顺序获取结果
可以使用Collections工具类里的reverse方法来进行动态数组的反转。
时间复杂度：O(n)，需要遍历树的所有节点
空间复杂度：O(n)

0 赞同 0 条回复

紫芝普通 2024年3月9日下午5:52

思路：暴力解法：层序遍历，对需要翻转的层单独进行翻转

func reverse(vec []int) () {
    n := len(vec)
    for i:=0; i<n/2; i++ {
        tmp := vec[i]
        vec[i] = vec[n-i-1]
        vec[n-i-1] = tmp
    }
    return
}
func decorateRecord(root *TreeNode) [][]int {
    var res [][]int
    if root == nil { return res }
    que := []*TreeNode{root}
    level := 0
    for len(que) > 0 {
        n := len(que)
        var tmp []int
        for i:=0; i<n; i++ {
            cur := que[i]
            tmp = append(tmp, cur.Val)
            if cur.Left!=nil { que = append(que, cur.Left) }
            if cur.Right!=nil { que = append(que, cur.Right) }
        }
        if level % 2 == 1 { reverse(tmp) }
        res = append(res, tmp)
        level++
        que = que[n:]
    }
    return res
}

0 赞同 0 条回复

【二叉树专题】多次被考察真题：剑指 Offer 32 – III. 从上到下打印二叉树

共以下 32 个回答

Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

# 回答此问题取消回复

【二叉树专题】多次被考察真题：剑指 Offer 32 – III. 从上到下打印二叉树

共以下 32 个回答

Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

# 回答此问题 取消回复

# 回答此问题取消回复