【二叉树专题】多次考察真题：剑指 Offer 32 – III. 从上到下打印二叉树-跟着帅地玩副业，开拓第二曲线PlayOffer

宁永久会员 2023年3月10日下午4:03

复习集合方面的知识

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        //思路基本一样，做每层的处理时反转
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> list = new ArrayList<>();
        queue.offer(root);
        boolean flag = true;
        while(!queue.isEmpty()){
            LinkedList<Integer> temp = new LinkedList<>();
            int k = queue.size();
            for(int i = 0; i < k; i ++){
                TreeNode node = queue.poll();
                if(flag){
                    temp.offerLast(node.val);
                }else{
                    temp.offerFirst(node.val);
                }
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            list.add(temp);
            flag = !flag;
        }
        return list;
    }
}

0 赞同 0 条回复

lucca 普通 2023年1月4日下午3:26

使用flag标记是否反转即可

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

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        boolean flag = false;
        while (!q.isEmpty()) {
            Queue<TreeNode> t = new LinkedList<>();
            List<Integer> res = new LinkedList<>();
            while (!q.isEmpty()) {
                TreeNode node = q.poll();
                res.add(node.val);
                if (node.left != null) t.add(node.left);
                if (node.right != null) t.add(node.right);
            }
            q = t;
            if (flag) Collections.reverse(res);
            flag = !flag;
            ans.add(res);
        }
        return ans;
    }
}

0 赞同 0 条回复

Gg 普通 2022年12月31日下午11:13

// 层序遍历
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Deque<TreeNode> dq = new ArrayDeque<>();
        dq.offerLast(root);
        boolean reverse = false;
        while(!dq.isEmpty()){
            int size = dq.size();
            List<Integer> currList = new ArrayList<>();
            for(int i = 0; i < size; i++){
                TreeNode curr = dq.pollFirst();
                currList.add(curr.val);
                if(curr.left != null){
                    dq.offerLast(curr.left);
                }
                if(curr.right != null){
                    dq.offerLast(curr.right);
                }
            }
            if(reverse){
                Collections.reverse(currList);
            }
            reverse = reverse == true ? false : true;
            res.add(currList);
        }
        return res;
    }
}

0 赞同 0 条回复

PatNick 普通 2022年12月21日下午1:37

def levelOrder(root: TreeNode):
    if root == None:
        return []
    res =  []
    # 利用队列
    queue = [root]
    # 判断是否需要反转列表
    deep = 1
    while not len(queue)==0:
        cur_list = []
        length = len(queue)
        for _ in range(length):
            cur_list.append(queue[_].val)
            if queue[_].left:
                queue.append(queue[_].left)
            if queue[_].right:
                queue.append(queue[_].right)

        queue = queue[length:]
        if deep % 2 == 0:
            cur_list = cur_list[::-1]
        res.append(cur_list)

    return res

0 赞同 0 条回复

如梦似歌普通 2022年12月18日下午3:55

class Solution {
    /**
     * 方法: 层序遍历 + 倒叙
     * 此方法的优点是只用列表即可，无需其他数据结构。
     * 复杂度分析:
     * 时间复杂度: T(n) = O(n); //BFS需要循环n次，共完成少于n个结点的倒叙操作，占用O(n)
     * 空间复杂度: S(n) = O(n); //最差情况下，即当树为满二叉树时，最多有n/2个树结点同时在queue中，使用O(n)大小的额外空间
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();  //初始化一个结果集，用来保存遍历的结果
        if(root == null){
            return list;  //如果树为空，则直接返回空列表[]即可
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode node;
        while(!queue.isEmpty()){
            //flag = !flag;  //每次循环时都对flag取非
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0 ; i--){
                node = queue.poll();
                tmp.add(node.val);
                if(node.left != null)
                    queue.add(node.left);
                if(node.right != null)
                    queue.add(node.right);
            }
            //偶数层倒序: 若结果集list的长度为奇数，说明当前是偶数层，则对tmp执行倒序操作
            if(list.size() % 2 == 1)
                Collections.reverse(tmp);  //当前遍历的层数是偶数层，需要将临时列表tmp进行反转
            list.add(tmp);
        }
        return list;
    }

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:16

非递归方法实现：（借助栈）
前序（中左右）
Class solution{
Public:
    Vertor<int> preorderTraversal(TresNode* root){
        Stack<TreeNode*> st;
        Vector<int> result;
        If(root==NULL) return result;
        St.push(root)；
        While(!st.empty()){
            TreeNode* node = st.top();
            St.pop();
            Result.push_back(node->val); //中
            If(node->right) st.push(node->right); //右
            If(node->left) st.push(node->left); //左 先右后左才是中左右
        }
        Return result;
    }
};


后序：
Class sloution{
Public:
    Vector<int>  postorderTraversal(TreeNode* root){
        Stack<TreeNode*> st;
        Vector<int> result;
        If(root==NULL) return result;
        St.push(root);
        While(!st.empty()){
            TreeNode* node  = st.top();
            St.pop();
            Result.push(node->val); //中
            If(node->left) st.push(root->left);//左
            If(node->right) st.push(root->right); //左右 //先左再右，是中右左
        }
        Reverse(result.left(),result.right()); //中右左，reverse变成左右中（后序）
        Return result;
    }
};


中序：借助指针访问（先访问最左下节点）
Class solution{
Public:
    Vector<int> inorderTraversal(TreeNode* root){
        Vector<int> result;
        Stack<TreeNode*> st;
        TreeNode* cur = root;
        While(cur!=NULL||!st.empty()){
            If(cur!=NULL){
                St.push(cur);
                Cur=cur->next;
            }else{
                Cur = st.top();
                St.pop();
                Result.push_back(cur->val);
                Cur=cur->right;
                }
            }
            Return result;
        }
    }
}；

0 赞同 0 条回复

cute. 普通 2022年11月19日上午11:20

var levelOrder = function(root) {
    if(root == null) {
        return [];
    }
    let queue = [root];
    let res = [];
    // 代表行数
    let level = 1;
    while(queue.length) {
        let len = queue.length;
        // 临时数组
        let tmp = [];
        for(let i = 0; i < len; i++) {
            // 把数组的第一个元素从其中删除，并返回第一个元素的值
            let node = queue.shift();
            // 奇数从左往右，偶数从右往左
            if(level % 2 === 1) {
                // 向数组的末尾添加一个或多个元素，并返回数组的新长度
                tmp.push(node.val);
            } else {
                // 将一个或多个元素添加到数组的开头并返回数组的长度
                tmp.unshift(node.val);
            }
            node.left &&　queue.push(node.left);
            node.right && queue.push(node.right);
        }
        res.push(tmp);
        level++;
    }
    return res;
};

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

0 赞同 0 条回复

xye 普通 2022年11月16日上午10:41

func levelOrder(root *TreeNode) [][]int {
    //定义二维数组
    res := [][]int{}
    if root == nil {
        return nil
    }

    queue := []*TreeNode{root}
    //i代表第i层
    for i := 0; len(queue) > 0; i++ {
        res = append(res, []int{})
        p := []*TreeNode{}
        //将当前层的队列结点打印到一个【】里
        for j := 0; j < len(queue); j++ {
            node := queue[j]
            res[i] = append(res[i], node.Val)
            if node.Left != nil {
                p = append(p, node.Left)
            }
            if node.Right != nil {
                p = append(p, node.Right)
            }
        }
        //偶数层反转
        if i % 2 == 1 {
            for m, n := 0, len(res[i]); m < n/2; m++ {
                res[i][m], res[i][n-m-1] = res[i][n-m-1], res[i][m]
            }
        }
        //将下一层节点队列赋值给queue
        queue = p

    }
    return res
}

O(n) O(n)

0 赞同 0 条回复

symbol 普通 2022年11月10日下午9:03

func levelOrder(root *TreeNode) (res [][]int) {
    if root == nil {
        return
    }
    stack1 := []*TreeNode{}// 定义一个主队列  用来遍历

    flag := true //定义一个信号 true为现在左孩子后右孩子 false为先右孩子后左孩子
    stack1 = append(stack1, root)
    for len(stack1) > 0{
        size := len(stack1)
        s := []int{}//定义一个存每一层节点值的数组
        stack2 := []*TreeNode{}// 定义一个孩子队列存当前节点的左后孩子
        for i := 0;i < size;i++{ //遍历每层的全部节点
            node := stack1[len(stack1)-1]
            stack1 = stack1[:len(stack1)-1]
            if node != nil{
                s = append(s, node.Val)  
                if flag == true{
                    if node.Left != nil{
                        stack2 = append(stack2, node.Left)
                    }
                    if node.Right != nil{
                        stack2 = append(stack2, node.Right)
                    }
                }else{
                    if node.Right != nil{
                        stack2 = append(stack2, node.Right)
                    }
                    if node.Left != nil{
                        stack2 = append(stack2, node.Left)
                    }  
                }
            }
        }
        //信号改变
        if flag == true{
            flag = false
        }else{
            flag = true
        }
        res = append(res, s) //收集每一层的值
        stack1 = stack2 //孩子队列赋给主队列
    }
    return
}

0 赞同 0 条回复

黎昕普通 2022年11月6日下午9:21

这道题在上一道题基础上加一个判断条件就行，没什么好说的

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        queue=collections.deque()
        tmp=collections.deque()
        level,res=[],[]
        queue.append(root)
        j=0
        while queue:
            node=queue.popleft()
            tmp.append(node)
            level.append(node.val)
            if not queue:
                j=j+1
                for i in range(len(tmp)):
                    node=tmp.popleft()
                    if node.left:queue.append(node.left)
                    if node.right:queue.append(node.right)
                if j%2==0:
                    level=level[::-1]
                res.append(level)
                level=[]
        return res

0 赞同 0 条回复

云雾里普通 2022年11月6日下午12:45

class Solution {
//队列+倒序
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res=new ArrayList<>();
        if(root!=null){
            queue.add(root);
        }
        while (!queue.isEmpty()){
            List<Integer> tmp= new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode poll = queue.poll();
                tmp.add(poll.val);
                if(poll.left!=null)queue.add(poll.left);
                if(poll.right!=null)queue.add(poll.right);
            }
            if(res.size()%2==1) Collections.reverse(tmp);
            res.add(tmp);
        }
        return res;
    }
}

0 赞同 0 条回复

刺猬普通 2022年11月5日下午5:47

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> out;
        vector<int> in;
        queue<TreeNode*> q;
        int n = 1; //n取1代表奇数行，0代表偶数行
        if(!root)
            return out;
        q.push(root);
        while(!q.empty()) {
            int k = q.size();
            while(k--) {
                TreeNode* node = q.front();
                q.pop();
                in.push_back(node->val);
                if(node->left)
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
            }
            if(n)
                n = 0;
            else {
                reverse(in.begin(), in.end());//reversereverse函数用于反转在[first,last)范围内的顺序（包括first指向的元素，不包括last指向的元素），reverse函数没有返回值
                n = 1;
            }
            out.push_back(in);  
            in.clear();
        }
        return out;
    }
};

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

0 赞同 0 条回复

浅夏的无奈普通 2022年11月4日下午10:50

//时间复杂度 O(n)
//空间复杂度 O(n)
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //创建收集容器
        List<List<Integer>> res = new ArrayList<>();
        //根节点判空
        if(root == null) return res;
        //创建辅助队列
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        //创建层次标记
        int count = -1;
        //循环遍历二叉树
        while(!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            count ++;
            int size = queue.size();
            for(int i=0;i < size; i++){
                TreeNode node = queue.poll();
                //根据层次进行遍历，奇数层直接添加，偶数层从队列尾部添加
                if(count%2==0){
                    list.add(node.val);
                }else{
                    list.add(0,node.val);
                }
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            res.add(list);
        }
        return res;
    }
}

0 赞同 0 条回复

星河普通 2022年11月4日下午6:41

层序+双端队列
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            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)

0 赞同 0 条回复

酥合普通 2022年11月3日下午11:40

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

        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        int level = 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(level % 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);
            level ++;
        }

        return res;
    }
}

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

0 赞同 0 条回复

@ 普通 2022年11月3日下午7:33

**时间复杂度 O(N) **
**空间复杂度 O(N) **

class Solution {

    //方法一：层序遍历 + 倒序
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> que = new LinkedList<>();

        if (root == null)
            return res;

        que.add(root);

        int n = 1;
        while (!que.isEmpty()) {
            int size = que.size();
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 0; i < size; i++) {
                TreeNode node = que.poll();
                list.add(node.val);

                if (node.left != null)
                    que.add(node.left);

                if (node.right != null)
                    que.add(node.right);
            }

            if (n % 2 == 0)
                Collections.reverse(list);

            n++;

            res.add(list);
        }

        return res;
    }

    //方法二：层序遍历 + 双端队列
    public List<List<Integer>> levelOrder2(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            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;
    }

}

0 赞同 0 条回复

一只骆驼普通 2022年11月3日下午2:51

用flag来转变每层元素的插入顺序

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        Deque<TreeNode> temp = new ArrayDeque<>();
        if(root==null) return ans;
        boolean flag = true;
        temp.add(root);
        while(!temp.isEmpty()){
            int size=temp.size();
            Deque<Integer> levelList = new LinkedList<Integer>();
            for(int i=0;i<size;i++){
                TreeNode cur = temp.poll();
                if(flag){
                    levelList.offerLast(cur.val);
                }else{
                    levelList.offerFirst(cur.val);
                }
                if(cur.left!=null) temp.add(cur.left);
                if(cur.right!=null) temp.add(cur.right);
            }
            flag=!flag;
            ans.add(new ArrayList<>(levelList));
        }
        return ans;
    }
}

0 赞同 0 条回复

狗蛋儿普通 2022年11月2日下午9:30

每一次注意反转的先后顺序，捋清楚堆是不能反转，反转的只能是vec

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if(root) que.push(root);
        vector<vector<int>> res;
        bool list =true;
        while(!que.empty()){ 
            int n = que.size();
            vector<int> vec;
            for(int i = 0;i<n;i++){
                TreeNode *Node = que.front();
                que.pop();
                vec.push_back(Node->val);
                if(Node->left) que.push(Node->left);
                if(Node->right) que.push(Node->right);
            }
            if(list){
                list = false;
            }else{
                reverse(vec.begin(),vec.end());
                list = true;
            }
            res.push_back(vec);
        }
        return res;
    }
}

0 赞同 0 条回复

cxxz 普通 2022年11月2日下午1:29

还是基于上一问的修改，res 中的vector个数代表了已经存放的层数，从第二层开始，奇数层倒序存放val，偶数层正序。

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (root == NULL)
             return res;
        vector<TreeNode *> nodes;
        nodes.push_back(root);
        traverse(nodes);
        return res;
    }

    void traverse(vector<TreeNode *> &curLevelNodes) {
        // base
        if (curLevelNodes.empty())
            return;
        vector<int> nodesVal;
        vector<TreeNode *> nextLevelNodes;
        // preorder 添加值和获取下一层节点
        for (auto node : curLevelNodes) {
            if ((res.size() % 2) == 0)
                nodesVal.push_back(node->val);
            else 
                nodesVal.insert(nodesVal.begin(), node->val);
            if (node->left != NULL)
                nextLevelNodes.push_back(node->left);
            if (node->right != NULL)
                nextLevelNodes.push_back(node->right);
        }
        res.push_back(nodesVal);
        traverse(nextLevelNodes);
    }  
};
时间复杂度O(n)
空间复杂度O(n)

0 赞同 0 条回复

lobort 普通 2022年11月2日上午1:04

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()){
            //设置每层的收集数组
            LinkedList<Integer> resLevel = new LinkedList<>();
            for(int i = queue.size(); i > 0 ; i--){
                TreeNode cur = queue.poll();

                resLevel.add(cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }

            }
            if(res.size() % 2 == 1){
            Collections.reverse(resLevel);
            }            
            res.add(resLevel);
        }
        return res;
    }
}

时间复杂度O(n) 空间复杂度O(n+m+k)
n是二叉树的空间 m是收集数组 k是每层数组

0 赞同 0 条回复

Error 普通 2022年11月1日下午9:39

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        stack = [root]
        tmp = []
        res = []
        q = len(stack)
        i = True
        while stack:
            v = stack.pop(0)
            if i:
                tmp.append(v.val)
            else:
                tmp.insert(0, v.val)
            if v.left:
                stack.append(v.left)
            if v.right:
                stack.append(v.right)
            if len(tmp) == q:
                res.append(tmp)
                tmp = []
                q = len(stack)
                i = i != True
        return res

时间复杂度 O(n)

0 赞同 0 条回复

Whatever 永久会员 2022年11月1日下午4:15

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

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        boolean flag = true;
        Queue<TreeNode> q = new LinkedList<>();
        List<List<Integer>> list = new ArrayList<>();
        q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            Deque<Integer> temp = new LinkedList<>();
            for(int i = 0;i < size;i++){
                TreeNode cur = q.poll();
                if(flag){
                    temp.offerLast(cur.val);
                }else{
                    temp.offerFirst(cur.val);
                }
                if(cur.left != null){
                    q.offer(cur.left);
                }
                if(cur.right != null){
                    q.offer(cur.right);
                }
            }  
            flag = !flag;
            list.add(new ArrayList<>(temp));
        }
        return list;
    }
}

0 赞同 0 条回复

小肸永久会员 2022年11月1日下午12:46

思路：和之前分层打印二叉树的思路一样，只不过需要把偶树层（从第一层起，没有第0层）的结果翻转，可以中res中进行翻转，也可以先翻转后，再加入res中。我是用一个双端队列先翻转后加入到res中，只不过deque存放是节点，leetcode官方题解deque存的是节点值，所以代码简洁，我的代码有些冗余。时间和空间复杂度都为O(N)。

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> temp = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return res;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        int level = 0;
        deque.addLast(root);
        while (!deque.isEmpty()) {
            int count = deque.size();
            level ++;
            temp = new ArrayList<>();
            if (level % 2 == 1) {
                for (int i = 0; i < count; i ++) {
                    TreeNode node = deque.pollFirst();
                    temp.add(node.val);
                    if (node.left != null) {
                        deque.addLast(node.left);
                    }
                    if (node.right != null) {
                        deque.addLast(node.right);
                    }
                    }
            } else {
                for (int i = 0; i < count; i ++) {
                    TreeNode node = deque.pollLast();
                    temp.add(node.val);
                    if (node.right != null) {
                        deque.addFirst(node.right);
                    }
                    if (node.left != null) {
                        deque.addFirst(node.left);
                    }
                }
            }
            res.add(temp);
        }
        return res;
    }
}

0 赞同 0 条回复

阿白普通 2022年11月1日上午7:05

通过双端队列缓存每一行，根据奇偶行分别进行后插和前插操作。最后转换为vector类型放到结果中
时间O（n），空间O（n）

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

        queue<TreeNode* > tree;
        vector<vector<int>> res;
        int order = 0;
        tree.push(root);
        while (!tree.empty())
        {
            int k = tree.size();
            deque<int> ans;
            for (int i = 0; i < k; ++i)
            {
                TreeNode *temp = tree.front();
                if (order % 2 == 0)
                    ans.push_back(temp->val);
                else
                    ans.push_front(temp->val);

                if (temp->left)
                    tree.push(temp->left);
                if (temp->right)
                    tree.push(temp->right);
                tree.pop();
            }

            order++;
            res.emplace_back(vector < int > {ans.begin(), ans.end()});
        }
        return res;
    }
};

0 赞同 0 条回复

Tolkien 永久会员 2022年10月31日下午11:03

/**
     * 辅助栈
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 1. 特殊情况
        if (root == null) {
            return new ArrayList<>();
        }

        // 2. 辅助队列用于储存每个节点的左右孩子，通过出队实现层序遍历
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        boolean isFromLeft = false;
        while (!queue.isEmpty()) {
            // 求队列大小以保证左右孩子都被出队
            int size = queue.size();
            LinkedList<Integer> temp = new LinkedList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();

                // isFromLeft用来判断是否逆序每层结点
                if (isFromLeft) {
                    temp.addFirst(node.val);
                }
                else {
                    temp.addLast(node.val);
                }

                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            isFromLeft = !isFromLeft;
            result.add(temp);
        }
        return result;
    }

0 赞同 0 条回复

波波_1936 普通 2022年10月31日下午9:18

/**
     * 剑指 Offer 32 - III. 从上到下打印二叉树 III
     */
    public List<List<Integer>> levelOrder3(TreeNode root) {
        //时间复杂度：O(n) 每个节点入队一次
        //空间复杂度 O(n) 最长队列中的元素小于n个
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean reserve = false;
        while (!queue.isEmpty()) {
            ArrayList<Integer> level = new ArrayList<>();
            int len = queue.size();
            while (len > 0) {
                TreeNode node = queue.poll();
                if (node != null) {
                    if (reserve) {
                        level.add(0, node.val);
                    } else {
                        level.add(node.val);
                    }
                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
                len--;
            }
            res.add(level);
            reserve = !reserve;
        }
        return res;
    }

0 赞同 0 条回复

庄重普通 2022年10月31日下午8:20

//  思路：
//     1.在从上到下打印二叉树II的基础上，添加一个标志来进行辨别层数
//     2.从右向左打印的时候，对数组直接进行头插
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        // deque<int> deq;
        vector<int> vec;

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

        TreeNode* pNode = root;
        que.push(pNode);
        int n = -1;
        int flag = 0;
        while(!que.empty()){
            n = que.size();

            for(int i = 0; i < n; ++i){
                pNode = que.front();
                if(flag % 2 == 0){
                    // deq.push_back(pNode->val);
                    vec.push_back(pNode->val);
                }
                else{
                    vec.insert(vec.begin(),pNode->val);
                    //deq.push_front(pNode->val);
                }

                if(pNode->left != NULL)
                    que.push(pNode->left);

                if(pNode->right != NULL)
                    que.push(pNode->right);

                que.pop();
            }

            // vRet.push_back(vector<int>(deq.begin(),deq.end()));
            // deq.clear();
            vRet.push_back(vec);
            vec.clear();
            ++flag;
        }

        return vRet;

    }

    queue<TreeNode*> que;
    vector<vector<int>> vRet;
};
//时间复杂度O(n) n为二叉树节点个数
//空间复杂度O(n) 借用一个队列空间进行辅助

0 赞同 0 条回复

T 普通 2022年10月31日下午5:11

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ll = new ArrayList<>();
        if(root == null) return ll;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int flag = 0;
        while(!queue.isEmpty()) {
            int len = queue.size();
            //用双端队列来实现之字型遍历
            LinkedList<Integer> l = new LinkedList<>();
            for(int i = 0; i < len; i++) {
                TreeNode tmp = queue.poll();
                // 通过flag标记奇数层和偶数层
                if(flag == 0) {    
                    l.addLast(tmp.val);
                } else {
                    l.addFirst(tmp.val);
                }
                if(tmp.left != null) queue.add(tmp.left);
                if(tmp.right != null) queue.add(tmp.right);
            }
            ll.add(l);
            flag = flag == 0 ? 1 : 0;
        }
        return ll;
    }
}

0 赞同 0 条回复

马啸天永久会员 2022年10月31日下午4:46

包含中文

    public List<List<Integer>> level(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用户永久会员 2022年10月31日下午3:30

class Solution {

    public List<List<Integer>> levelOrder(TreeNode root) {

        Queue<TreeNode> queue = new LinkedList<>();

        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        queue.add(root);
        while(!queue.isEmpty()) {

            List<Integer> tmp = new ArrayList<>();

            for(int i = queue.size(); i > 0; i--) {

                TreeNode node = queue.poll();

                tmp.add(node.val);

                if(node.left != null) queue.add(node.left);

                if(node.right != null) queue.add(node.right);

            }

            if(res.size() % 2 == 1) Collections.reverse(tmp);

            res.add(tmp);

        }

        return res;

    }

}

时间空间复杂度O(n)
有俩种比较简单的方法，这个直接将偶数层的Tmp反转。

0 赞同 0 条回复

y 普通 2022年10月31日下午3:23

var levelOrder = function(root) {
  if(!root) return [];
  let queue = [root];
  let res = [];
  let level = 1;
  while(queue.length) {
      let n = queue.length;
      let cur = [];
      for(let i =0; i < n; i++) {
          let node = queue.shift();
        //   奇数行从后入，偶数行从前入
          if(level % 2 === 1) {
               cur.push(node.val);
          } else {
               cur.unshift(node.val);
          }
          node.left && queue.push(node.left);
          node.right && queue.push(node.right)
      }
      res.push(cur);
      level++;
  }
  return res;
};

层序遍历

0 赞同 0 条回复

绍熙普通 2022年10月31日下午1:41

解题思路：
利用双端队列的两端皆可添加元素的特性，设打印列表（双端队列） tmp ，并规定：
奇数层则添加至 tmp 尾部，
偶数层则添加至 tmp 头部。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            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;
    }
}

0 赞同 0 条回复

just 普通 2022年10月31日下午12:20

//队列、、
class Solution {
public:
vector<vector> res;
void fun(TreeNode* root,int num){
if(!root) return;
if(numres.size()) res.push_back(vector{});
res[num].push_back(root->val);
fun(root->left,num+1);
fun(root->right,num+1);
return;
}

vector<vector<int>> levelOrder(TreeNode* root) {
    fun(root,0);
    for(int i=0;i<res.size();++i){
        if(i%2){
            reverse(res[i].begin(),res[i].end());
        }
    }
    return res;

}

};

0 赞同 0 条回复

是梦终空永久会员 2022年10月31日上午11:30

和前一个题差不多，多了一个奇偶判断，
时间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 条回复

追普通 2022年10月31日上午10:57

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> stc;
        if(root == nullptr) return stc;
        queue<TreeNode*> q;
        q.push(root);
        bool isDos = true;
        while(!q.empty()){
            deque<int> val;
            int size = q.size();
            for(int i = 0; i < size; i++){
                TreeNode* front = q.front();
                q.pop();
                if(isDos)   val.push_back(front->val);
                else        val.push_front(front->val);

                if(front->left) q.push(front->left);
                if(front->right) q.push(front->right);
            }
            stc.push_back(vector<int>(val.begin(), val.end()));
            isDos = !isDos;
        }
        return stc;
    }
};

注意：双端队列deque中的push_back为正序，push_front为逆序，为了保证函数返回的类型为vector<vector>，还需要额外进行一次vector(val.begin(), valend())处理

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年10月31日上午10:41

时间空间复杂度为O（n）

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

0 赞同 0 条回复

派大星普通 2022年10月31日上午10:40

class Solution {
//使用工具类Collections的reverse方法直接对集合反转
//时间复杂度O(n)
//空间复杂度O(n)
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null){
            return new ArrayList<>();
        }
        TreeNode temp = root;
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.add(root);
        List<List<Integer>> lists = new ArrayList<>();
        while (!queue1.isEmpty()||!queue2.isEmpty()) {
            List<Integer> nodes = new ArrayList<>();
            if(queue2.isEmpty()) {
                while (!queue1.isEmpty()) {
                    TreeNode node = queue1.remove();
                    nodes.add(node.val);
                    if (node.left != null) queue2.add(node.left);
                    if (node.right != null) queue2.add(node.right);
                }
                lists.add(nodes);
            }else if(queue1.isEmpty()){
                while (!queue2.isEmpty()) {
                    TreeNode node = queue2.remove();
                    nodes.add(node.val);
                    if (node.left != null) queue1.add(node.left);
                    if (node.right != null) queue1.add(node.right);
                }
                Collections.reverse(nodes);
                lists.add(nodes);
            }
        }

        return lists;
    }
}

0 赞同 0 条回复

你有点可爱喔普通 2022年10月31日上午10:08

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

/**
 * 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) {
            if(root == null){
                return new ArrayList<>();
            }
            Queue<TreeNode> queue = new LinkedList<>();
            List<List<Integer>>res = new ArrayList<>();
            queue.add(root);
            int count  = 1;
            while(!queue.isEmpty()){
                int k = queue.size();
                LinkedList<Integer> temp = new LinkedList<>();
                for(int i = 0;i<k;i++){
                    TreeNode t1 = queue.poll();
                    if(count % 2 == 1){
                        temp.add(t1.val);
                    }else{
                        temp.addFirst(t1.val);
                    }
                    //添加左右结点 到队列中去
                    if(t1.left!=null)queue.add(t1.left);
                    if(t1.right!=null)queue.add(t1.right);
                }
                res.add(temp);
                count++;
            }
            return res;
    }
}

0 赞同 0 条回复

天然普通 2022年10月31日上午12:44

双向链表不会，还得继续学习，关键在于奇偶的，时间复杂度为O(n),空间复杂度为O(n)

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:    
        if not root: return []
        num = [root]
        res = []
        while num:
            k,tem= [],collections.deque()
            for i in num:
                if len(res)%2:tem.appendleft(i.val)
                else: tem.append(i.val)
                if i.left: k.append(i.left)
                if i.right: k.append(i.right)                     
            num = k
            if tem :res.append(list(tem))

        return res

0 赞同 0 条回复

青木普通 2022年10月31日上午12:26

/**
    太困了想先睡了想的暴力方法
    用队列和栈各保存一次层节点，唯一不足的是要在栈那里用另一个栈反转一下顺序

    时间复杂度O(n)
    空间复杂度O(n)
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        ArrayList<List<Integer>> ans = new ArrayList<List<Integer>>();
        Queue<TreeNode> q = new LinkedList<>();
        Deque<TreeNode> s = new ArrayDeque<>();
        if(root==null) return ans;

        q.offer(root);
        while(!q.isEmpty() || !s.isEmpty()){
            ArrayList<Integer> layer = new ArrayList<>();
            if(!q.isEmpty()){
                while(!q.isEmpty()){
                    TreeNode node = q.poll();
                    layer.add(node.val);
                    if(node.left != null) s.push(node.left);
                    if(node.right != null) s.push(node.right);
                }
            }
            else if(!s.isEmpty()){
                Deque<TreeNode> s2 = new ArrayDeque<>();
                while(!s.isEmpty()){
                    TreeNode node = s.pop();
                    layer.add(node.val);
                    s2.push(node);
                }

                while(!s2.isEmpty()){
                    TreeNode node = s2.pop();
                    if(node.left != null) q.offer(node.left);
                    if(node.right != null) q.offer(node.right);
                }
            }
            ans.add(layer);
        }
        return ans;
    }
}

0 赞同 0 条回复

yanshuojune 普通 2022年10月30日下午11:43

解题思路：增加一个对当前层是奇数层还是偶数层的判断，从而决定是正序还是倒序
时间复杂度：O(n)
空间复杂度：O(n)

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        res = []
        queue = [root]
        while queue:
            sub_res = []
            for i in range(len(queue)):
                cur_node = queue.pop(0)
                # 奇数层（root为第0层）
                if len(res) % 2:
                    sub_res.insert(0,cur_node.val)
                # 偶数层
                else:
                    sub_res.append(cur_node.val)
                if cur_node.left:
                    queue.append(cur_node.left)
                if cur_node.right:
                    queue.append(cur_node.right)
            res.append(sub_res)
        return res

0 赞同 0 条回复

So 普通 2022年10月30日下午10:53

/**
 * 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) {
        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;
    }
}

时间：O(n)，空间：O(n)

0 赞同 0 条回复

訁訁訁訁訁普通 2022年10月30日下午10:07

使用Collections偶数行反转？(学的)

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            for(int i = 0;i < size;i++){
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if(cur.left != null) queue.offer(cur.left);
                if(cur.right != null) queue.offer(cur.right);
            }
            ret.add(list);
        }
        for(int i=1;i<ret.size();i+=2){
            Collections.reverse(ret.get(i));
        }
        return ret;
    }
}

使用LinkedList特性模拟双端队列

时间复杂度 O(N) ： N 为二叉树的节点数量，即 BFS 需循环 N 次，占用 O(N) ；双端队列的队首和队尾的添加和删除操作的时间复杂度均为 O(1)
空间复杂度 O(N) ：最差情况下，即当树为满二叉树时，最多有 N/2 个树节点同时在 deque 中，使用 O(N) 大小的额外空间。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        queue.offer(root);
        int depth = 1;
        while(!queue.isEmpty()){
            LinkedList<Integer> list = new LinkedList<>();
            int size = queue.size();
            for(int i = 0;i < size;i++){
                TreeNode cur = queue.poll();
                if(depth % 2 == 1){
                    //奇数
                    list.add(cur.val);
                }else{
                    //偶数前插
                    list.addFirst(cur.val);
                }
                if(cur.left != null) queue.offer(cur.left);
                if(cur.right != null) queue.offer(cur.right);
            }
            depth++;
            ret.add(list);
        }
        return ret;
    }
}

优化，一次循环奇数偶数层同时进行

奇数层：从左向右打印，先左后右加入下层节点

偶数层：从右向左打印，先右后左加入下层节点

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        deque.add(root);
        while(!deque.isEmpty()){
            List<Integer> list = new ArrayList<>();

            for(int i = deque.size();i > 0;i--){
                TreeNode cur = deque.removeFirst();
                list.add(cur.val);
                //先左后右加入下层节点
                if(cur.left != null) deque.addLast(cur.left);
                if(cur.right != null) deque.addLast(cur.right);
            }
            ret.add(list);
            if(deque.size() == 0) break;
            list = new ArrayList<>();
            for(int i = deque.size();i > 0;i--){
                TreeNode cur = deque.removeLast();
                list.add(cur.val);
                // 先右后左加入下层节点
                if(cur.right != null) deque.addFirst(cur.right);
                if(cur.left != null) deque.addFirst(cur.left);
            }
            ret.add(list);
        }
        return ret;
    }
}

0 赞同 0 条回复

单个酒窝儿普通 2022年10月30日下午8:18

和上一题差不多，只不过在这一题填加一个变量用来判别是奇数行和偶数行
时间复杂度O(n) 空间复杂度O(n)

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> vec1;
        queue<TreeNode*> que;
        if(root == NULL) return vec1;
        que.push(root);
        int i = 1;
        while(!que.empty()){
            vector<int> vec2;
            int k = que.size();
            for(int i = 0;i < k;i++){
                TreeNode* tmp = que.front();
                que.pop();
                vec2.push_back(tmp->val);
                if(tmp->left != NULL) que.push(tmp->left);
                if(tmp->right != NULL) que.push(tmp->right);
            }
            if(i%2 == 1){
                vec1.push_back(vec2);
            }
            else{
                reverse(vec2.begin(),vec2.end());
                vec1.push_back(vec2);
            }
            i++;

        }
        return vec1;
    }
};

0 赞同 0 条回复

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

共以下 44 个回答

使用flag标记是否反转即可

# 回答此问题取消回复

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

共以下 44 个回答

使用flag标记是否反转即可

# 回答此问题 取消回复

# 回答此问题取消回复