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

hi 普通 2023年8月9日下午3:56

奇偶数行打印的顺序不一样，设置标志判断当前行到底是奇数行还是偶数行
如果是偶数行就反转数组

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if(root) q.push(root);
        bool flag = true;
        while(q.size()){
            int len = q.size();
            vector<int> level;
            while(len--){
                TreeNode* t = q.front();
                level.push_back(t->val);

                q.pop();
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            if(flag == false) reverse(level.begin(), level.end());
            flag = !flag;
            res.push_back(level);
        }
        return res;
    }
};

0 赞同 0 条回复

今天没时间刷题普通 2023年8月1日下午11:40

时间On，空间On
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(!root) return res;

        queue<TreeNode*> q;
        q.push(root);
        int line{1};
        while(!q.empty())
        {
            int num = q.size();
            deque<int> tempDeq;
            while(num--)
            {
                TreeNode* temp = q.front();
                q.pop();

                if(line % 2 == 1)
                {
                    tempDeq.push_back(temp->val);
                }
                else
                {
                    tempDeq.push_front(temp->val);
                }
                if(temp->left) q.push(temp->left);
                if(temp->right) q.push(temp->right);

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

0 赞同 0 条回复

小季同学普通 2023年7月26日下午10:51

ts

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function levelOrder(root: TreeNode | null): number[][] {
    // 边界判断
    if(!root) return []
    const queue: TreeNode[] = [root]
    const result: number[][] =[]
    // 标记是技术行还是偶数行
    let sum:number = 1
    while(queue.length) {
        let level: number[] = []
        let levelSize: number = queue.length
        for(let i = 0; i < levelSize; i++) {
            const node = queue.shift()
            // 奇数行
            if(sum % 2 === 1) {
                level.push(node.val)
            }else {
                level.unshift(node.val)
            }
            if(node.left) queue.push(node.left)
            if(node.right) queue.push(node.right)
        }
    sum++
    result.push(level)
    }
    return result
};

0 赞同 0 条回复

doordie. 普通 2023年7月25日上午10:04

   public List<List<Integer>> levelOrder2(TreeNode root) {
       // 1.特例处理
        if (root == null) {
            return new ArrayList<>();
        }
        // 2.初始化
        // 返回结果
        List<List<Integer>> res = new ArrayList<>();
        // 双端队列deque
       Queue<TreeNode> queue =  new LinkedList<>();
        // 3.算法流程
        while (!queue.isEmpty()){
            //3.1 临时列表存储每层结果
            LinkedList<Integer> tmp = new LinkedList<>();
            //3.2 对当前层循环打印  循环次数为队列长度
            for (int i = queue.size(); i > 0; i--){
                //3.2.1 出队
                TreeNode node = queue.poll();
                //3.2.2 偶数层 加到头部
                if (res.size() % 2 == 0){
                    tmp.addFirst(node.val);
                }else {
                    // 奇数层 加到尾部
                    tmp.addLast(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 条回复

ppopp 普通 2023年7月20日上午12:24

//用双端队列
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector> zigzagLevelOrder(TreeNode root) {
vector<vector> ans;
if (!root) {
return ans;
}

    queue<TreeNode*> nodeQueue;
    nodeQueue.push(root);
    bool isOrderLeft = true;

    while (!nodeQueue.empty()) {
        deque<int> levelList;
        int size = nodeQueue.size();
        for (int i = 0; i < size; ++i) {
            auto node = nodeQueue.front();
            nodeQueue.pop();
            if (isOrderLeft) {
                levelList.push_back(node->val);
            } else {
                levelList.push_front(node->val);
            }
            if (node->left) {
                nodeQueue.push(node->left);
            }
            if (node->right) {
                nodeQueue.push(node->right);
            }
        }
        ans.emplace_back(vector<int>{levelList.begin(), levelList.end()});
        isOrderLeft = !isOrderLeft;
    }

    return ans;
}

};

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月19日下午10:44

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root==null) return result;
        queue.offer(root);
        boolean flag = true;
        while(!queue.isEmpty()){
            int k = queue.size();
            // 奇数行，从左到右打印；偶数行从右到左打印
            LinkedList<Integer> cur = new LinkedList<>();
            while(k!=0){
                TreeNode temp = queue.poll();
                if(flag == true){
                    cur.add(temp.val);
                }
                if(flag == false){
                    // 之前是从后插入，就相等于从左到右
                    // 现在从前插入，就相等于从右到左（逆序）
                    cur.addFirst(temp.val);
                }
                // 入队顺序不变，只是打印顺序变了
                if(temp.left!=null) queue.offer(temp.left);
                if(temp.right!=null) queue.offer(temp.right);
                k--;
            }
            result.add(cur);
            // 这层结束
            flag = !flag;
        }
        return result;
    }
}

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

0 赞同 0 条回复

北辰普通 2023年7月18日下午9:05

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root==null) return ans;
        int level=0;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()) {
            level++;
            List<Integer> list = new ArrayList<>();
            int size=q.size();
            while(size-->0) {
                TreeNode node = q.poll();
                list.add(node.val);
                if(node.left!=null) q.offer(node.left);
                if(node.right!=null) q.offer(node.right);
            }
            if(level%2==1) {
                ans.add(list);
            }else {
                Collections.reverse(list);
                ans.add(list);
            }
        }
        return ans;
    }

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

0 赞同 0 条回复

片言莫语普通 2023年7月18日下午8:02

/**
 * 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 LinkedList<>();
       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 条回复

Mby 普通 2023年7月18日下午2:35

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

0 赞同 0 条回复

mpweixin用户普通 2023年7月18日上午11:01

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root==null)
            return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        //flag为1正序，为-1逆序，轮换正负做标记
        int flag = 1;
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int k = queue.size();
            for (int i = 0; i < k; i++) {
                TreeNode poll = queue.poll();
                list.add(poll.val);
                if (poll.left!=null) queue.offer(poll.left);
                if (poll.right!=null) queue.offer(poll.right);
            }
            if (flag==1) {
                res.add(list);
                flag=flag*-1;
            } else if (flag==-1) {
                List<Integer> list1 = new ArrayList<>(list.size());
                for (int i = list.size()-1; i >= 0; i--) {
                    list1.add(list.get(i));
                }
                res.add(list1);
                flag=flag*-1;
            }
        }
        return res;
    }

0 赞同 0 条回复

普通 2023年7月17日下午11:30

在第二题的基础上加个行数的判断
class Solution
{
vector<vector> cc;
queue<TreeNode> Inqueue;
public:
vector<vector> levelOrder(TreeNode root)
{
if(!root) return cc;
Inqueue.push(root);
int tt;
while(Inqueue.size())
{
int l=Inqueue.size();
vector lever;

         for(int i=0;i<l;i++)
         {
          TreeNode* temp=Inqueue.front();
          lever.push_back(temp->val);
         if(temp->left) Inqueue.push(temp->left);
         if(temp->right) Inqueue.push(temp->right);
         Inqueue.pop();
         }
        if(tt%2==1)
        {
            vector<int> v;
          for(int ii=lever.size()-1;ii>=0;ii--)
                    v.push_back(lever[ii]);  
            cc.push_back(v); 
        }
       else
       {
           cc.push_back(lever); 
       }
         tt++;
     }
     return cc;
}

};

0 赞同 0 条回复

CKX 普通 2023年7月17日下午7:16

func levelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    if root == nil {
        return res
    }
    queue := []*TreeNode{root}
    flag := true //true 向右  flase向左
    for len(queue) > 0 {
        length := len(queue)
        temp := []int{}
        for i := 0; i < length; i++ {
            node := queue[0]
            queue = queue[1:]
            if flag {
                temp = append(temp, node.Val)
            } else {
                temp = append([]int{node.Val}, temp...)
            }

            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        flag = !flag
        res = append(res, temp)
    }
    return res
}

0 赞同 0 条回复

June 普通 2023年7月17日下午5:42

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
import "container/list"
func reverseArray(arr []int) {
    n := len(arr)
    for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
        arr[i], arr[j] = arr[j], arr[i]
    }
}
func levelOrder(root *TreeNode) [][]int {
    var ans [][]int 
    if root == nil {
        return ans
    }

    var deep int = 0
    var queue = list.New()
    queue.PushBack(root)

    for queue.Len() != 0 {
        size := queue.Len()
        var tmp []int
        for i:=0 ; i< size ; i++ {
            node := queue.Front().Value.(*TreeNode)
            queue.Remove(queue.Front())
            tmp = append(tmp,node.Val)
            if node.Left != nil {
                queue.PushBack(node.Left)
            }
            if node.Right != nil {
                queue.PushBack(node.Right)
            }
        }
        if deep % 2 == 1 {
            reverseArray(tmp) //逆序
        }
        deep++
        ans = append(ans,tmp)
    }
    return ans
}

0 赞同 0 条回复

艺普通 2023年7月17日下午4:43

“`c++
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:
vector> levelOrder(TreeNode* root) {
vector> res;
int i;
int judge=1;
if(!root) return res;
queue q;
q.push(root);
while(!q.empty())
{
int k=q.size();
vector lev;
for(i=0;ival);
if(tmp->left) q.push(tmp->left);
if(tmp->right) q.push(tmp->right);
}
if(judge%2==0) reverse(lev.begin(),lev.end());//通过奇偶判断反转
res.push_back(lev);
judge++;
}
return res;
}
};

0 赞同 0 条回复

NullPointerException 普通 2023年7月17日下午3:30

class Solution {
public List<List> levelOrder(TreeNode root) {
//通过奇偶判断翻转
int jude =1;
List<List> reuslt =new ArrayList<List>();
List temp ;
if(root null) return reuslt;
Queue queue =new LinkedList();
queue.add(root);
int i= 1;
while(!queue.isEmpty())
{
i =queue.size();
temp =new ArrayList();
while(i>0)
{
TreeNode node =queue.remove();
i–;
if(node.left!=null)
{
queue.add(node.left);
}
if(node.right!=null)
{
queue.add(node.right);
}
temp.add(node.val);
}
if(jude%2!=1)
{
Collections.reverse(temp);

            }

        reuslt.add(temp);
        jude++;
    }
    return reuslt;
}

}

0 赞同 0 条回复

V2ero 普通 2023年7月17日上午10:14

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

 function levelOrder(root: TreeNode | null): number[][] {
     if (!root) return [];
    const queue: Array = [root];
    const res: number[][] = [];
    let count = 1;
    while (queue.length) {
        const len = queue.length;
        const lev: number[] = [];
        for (let i = 0; i < len; i += 1) {
            const node = queue.shift();
            if (count % 2 === 0) {
                lev.unshift(node?.val);
            } else {
                lev.push(node?.val);
            }
            node?.left && queue.push(node.left);
            node?.right && queue.push(node.right);
        }
        res.push(lev);
        count += 1;
    }
    return res;
};

0 赞同 0 条回复

CaCO3 永久会员 2023年7月17日上午9:31

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

}
”’
时间复杂度：O(n)
空间复杂度O(n)

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月16日下午9:57

代码

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 sum=1;
        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 条回复

神经蛙普通 2023年7月16日下午4:06

/**
    时间复杂度O(n)
    空间复杂度O(n)
    双端队列
*/
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();

        if (root == null) {
            return res;
        }      

        // 入队
        queue.add(root);

        // 处理每一层
        while(!queue.isEmpty()) {
            LinkedList<Integer> tmp = new LinkedList<>();
            int size = queue.size();
            // 处理一层
            for (int i = 0; i < size; ++i) {
                TreeNode node = queue.removeFirst();

                // 判断奇偶数，由0开始
                if (res.size() % 2 == 0) {
                    // 偶数层：0、2、4...，左 -> 右
                    tmp.addLast(node.val);
                } else {
                    // 奇数层：1、3、5...，右 -> 左
                    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 条回复

Marshan 普通 2023年7月16日下午1:43

II. 从上到下打印二叉树加入一个判断, reverse中间vector即可

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(!root){
            return res;
        }
        queue<TreeNode *>queue;
        queue.push(root);
        int level = 1;
        while(!queue.empty()){
            int n = queue.size();
            vector<int> temp;
            for(int i = 0;i < n;++i){
                auto t = queue.front();
                queue.pop();
                temp.push_back(t->val);
                if(t->left){
                    queue.push(t->left);
                }
                if(t->right){
                    queue.push(t->right);
                }
            }
            if(level % 2 == 0){
                reverse(temp.begin(),temp.end());
            }
            res.push_back(temp);
            level++;

        }
        return res;
    }
};

0 赞同 0 条回复

人生何处不青山普通 2023年7月16日上午10:57

用一个变量来控制一下奇偶层

function levelOrder(root: TreeNode | null): number[][] {
    if(!root) return [];
    let res : number[][] = [];
    let queue: TreeNode[] = [];
    let order: boolean = false; // false从左到右 true反之
    queue.push(root);
    while(queue.length) {
        let len = queue.length;
        let tmp: number[] = [];
        while(len--) {
            let node = queue.shift();
            tmp.push(node.val);
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        if(order) {
            tmp.reverse();
        }
        order = !order;
        res.push(tmp);
    }
    return res;
};

0 赞同 0 条回复

波雅汉库克普通 2023年7月16日上午10:11

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root == nullptr){
            return res;
        }
        deque<TreeNode*> dq;
        dq.push_back(root);
        int numLvl = 1;
        while(!dq.empty()){
            vector<int> level;
            int len = dq.size();
            while(len--){
                TreeNode* cur = dq.front();
                dq.pop_front();
                if(cur->left){
                    dq.push_back(cur->left);
                }
                if(cur->right){
                    dq.push_back(cur->right);
                }
                level.push_back(cur->val);
            }
            if(numLvl%2 == 0){
                vector<int> reverlvl;
                for(int i = level.size()-1; i<0; i--){
                    reverlvl.push_back(level[i]);
                }
                res.push_back(reverlvl);
            }
            else{
                res.push_back(level);
            }

        }
        return res;
    }
};

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

0 赞同 0 条回复

周小二普通 2023年7月16日上午3:37

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        List<List<Integer>> result = new ArrayList<>();
        boolean flag = true;
        if (root != null) {
            deque.addFirst(root);
        }
        while(!deque.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            if (flag) {
                //由左到右打印，由左到右插入
                for (int i = deque.size(); i > 0; i--) {
                    TreeNode node = deque.removeFirst();
                    tmp.add(node.val);
                    if (node.left != null) deque.addLast(node.left);
                    if (node.right != null) deque.addLast(node.right);
                }
            } else {
                //由右到左打印，由右到左插入
                for (int i = deque.size(); i > 0; i--) {
                    TreeNode node = deque.removeLast();
                    tmp.add(node.val);
                    if (node.right != null) deque.addFirst(node.right);
                    if (node.left != null) deque.addFirst(node.left);
                }
            }
            result.add(tmp);
            flag = !flag;
        }
        return result;
    }
}

0 赞同 0 条回复

阿尚普通 2023年7月16日上午12:00

//利用双端队列可以从队头和队尾插入
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();

        if(root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int flag = 1;

        while(!queue.isEmpty()){
            int layerSize = queue.size();
            LinkedList<Integer> list = new LinkedList<>();
            for(int i = 0; i < layerSize; i++){
                TreeNode node = queue.poll();
                if(flag == 1){
                    list.offerLast(node.val);
                }else{
                    list.offerFirst(node.val);
                }

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

        return result;
    }
}

0 赞同 0 条回复

#00456B 普通 2023年7月15日下午10:36

思路

一样是层序遍历，需要做的就是控制从左到右还是从右到左，这个通过一个flag来控制。
需要注意的是，每一行的val值不再通过vector来进行存储，因为vector只能push_back，这里采用deque双向队列来实现，deque能够实现push_back和push_front。
然后通过vector\<int>把deque的类型进行强转，存入ans

代码

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(root == NULL){
            return ans;
        }
        queue<TreeNode*> que;
        que.push(root);
        bool flag = 1;
        while(!que.empty()){
            int size = que.size();
            deque<int> res;
            while(size--){
                TreeNode* temp = que.front();
                if(flag == 1){
                    res.push_back(temp->val);
                }
                else{
                    res.push_front(temp->val);
                }
                if(temp->left) que.push(temp->left);
                if(temp->right) que.push(temp->right);
                que.pop();
            }
            flag = !flag;
            ans.push_back(vector<int>(res.begin(),res.end()));
        }
        return ans;
    }
};

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月15日下午10:18

Day8：下面是代码

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();    
        if(root != null) q.offer(root);
        while(!q.isEmpty()){
            //双端队列用LinkedList来实现
            LinkedList<Integer> tmp = new LinkedList<>(); 
            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.offer(node.left);
                if(node.right != null) q.offer(node.right);
            }
            res.add(tmp);
        }    
        return res;
    }
}

0 赞同 0 条回复

Luminous 普通 2023年7月15日下午6:31

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 条回复

枫梓。普通 2023年7月15日下午6:28

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

也可以用双端队列，双O(n)

0 赞同 0 条回复

Mooby 普通 2023年7月15日下午5:57

八
/**
* 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> levelOrder(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.add(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 条回复

AD钙奶普通 2023年7月15日下午5:17

这题稍微复杂一点，对打印顺序有了要求。
说重点：
对层数进行判断，分奇数层偶数层来进行相应操作
可以从队列加入或删除的顺序来控制，这里用双端队列是很好的选择。
也可以从集合的加入顺序来控制，LinkedList在这里使用再合适不过，它可以头插，也可以尾插。
我个人认为第2种方法，更加简洁。

贴两种方法

控制集合加入的顺序

class Solution {
    public List> levelOrder(TreeNode root) {
        List> res = new ArrayList<>();
        Deque deque = new ArrayDeque<>();
        if(root != null) deque.addLast(root);
        while(!deque.isEmpty()) {
            LinkedList list = new LinkedList<>();
            int size = deque.size();
            int cnt = res.size() % 2;
            for(int i = 0; i < size; i ++) {
                TreeNode node = deque.removeFirst();
                if(cnt == 0) {
                    list.addLast(node.val);
                } else {
                    list.addFirst(node.val);
                }
                if(node.left != null) deque.addLast(node.left);
                if(node.right != null) deque.addLast(node.right);
            }
            res.add(list);
        }
        return res;
    }
}

控制队列加入和删除的顺序

class Solution {
    public List> levelOrder(TreeNode root) {
        List> res = new ArrayList<>();
        Deque deque = new ArrayDeque<>();
        if(root == null) return new ArrayList<>();
        deque.addLast(root);
        int cnt = 0;
        while(!deque.isEmpty()) {
            cnt ++;
            List list = new ArrayList<>();
            int size = deque.size();
            for(int i = 0; i < size; i ++) {
                TreeNode node = deque.removeFirst();
                list.add(node.val);
                if(node.left != null) deque.addLast(node.left);
                if(node.right != null) deque.addLast(node.right);
            }
            res.add(list);
            if(deque.isEmpty()) break;

            list = new ArrayList<>();
            size = deque.size();
            for(int i = 0; i < size; i ++) {
                TreeNode node = deque.removeLast();
                list.add(node.val);
                if(node.right != null) deque.addFirst(node.right);
                if(node.left != null) deque.addFirst(node.left);
            }
            res.add(list);
        }
        return res;
    }
}

写在最后：选择合适的数据结构解题很重要！

0 赞同 0 条回复

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

共以下 30 个回答

思路

代码

贴两种方法

控制集合加入的顺序

控制队列加入和删除的顺序

# 回答此问题取消回复

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

共以下 30 个回答

思路

代码

贴两种方法

控制集合加入的顺序

控制队列加入和删除的顺序

# 回答此问题 取消回复

# 回答此问题取消回复