2018网站做外链,镇海建设交通局网站首页,帝国CMS做的淘客网站,域名进行网站备案吗103.给你二叉树的根节点 root #xff0c;返回其节点值的 锯齿形层序遍历 。#xff08;即先从左往右#xff0c;再从右往左进行下一层遍历#xff0c;以此类推#xff0c;层与层之间交替进行#xff09;。 示例 1#xff1a; 输入#xff1a;root [3,9,20,null,null,… 103.给你二叉树的根节点 root 返回其节点值的 锯齿形层序遍历 。即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。 示例 1 输入root [3,9,20,null,null,15,7] 输出[[3],[20,9],[15,7]] 示例 2 输入root [1] 输出[[1]] 示例 3 输入root [] 输出[] 我的原始人解法层序遍历每次处理一遍从左到右的和从右到左的遍历可以直接略过不看 public ListListInteger zigzagLevelOrder(TreeNode root) {ListListInteger res new ArrayList();if(rootnull)return res;StackTreeNode stack new Stack();stack.push(root);while(!stack.isEmpty()){ListInteger temp new ArrayList();StackTreeNode tempStack new Stack();// 从左到右遍历节点// stack 从左到右存节点下面的遍历取的时候就相当于从右到左遍历for(int istack.size();i0;i--){TreeNode node stack.pop();temp.add(node.val);if(node.left ! null)tempStack.push(node.left);if(node.right ! null)tempStack.push(node.right);}stacktempStack;tempStack new Stack();res.add(temp);temp new ArrayList();// 从右到左遍历节点因为上面是用 stack 从左到右存的// stack 从右到左存节点下一轮的遍历取的时候就相当于从左到右遍历for(int istack.size();i0;i--){TreeNode node stack.pop();temp.add(node.val);if(node.right ! null)tempStack.push(node.right);if(node.left ! null)tempStack.push(node.left);}stacktempStack;// 如果到这已经遍历完了就不用加了if(temp.size()0)res.add(temp);}return res;}他人解法1层序遍历用一个变量记录是从左到右还是从右到左存放当前层的值这样每次遍历都从左到右放节点即可具体看代码 public ListListInteger zigzagLevelOrder(TreeNode root) {ListListInteger res new ArrayList();if(rootnull)return res;boolean leftToRight true;QueueTreeNode queue new LinkedList();queue.add(root);while(!queue.isEmpty()){ListInteger temp new ArrayList();for(int iqueue.size();i0;i--){TreeNode node queue.poll();// 从左到右正常放if(leftToRight)temp.add(node.val);// 遍历节点的顺序为从左到右每次把值放首位// 这样就相当于从右到左存放了这层的结点的值else temp.add(0,node.val);if(node.left ! null)queue.add(node.left);if(node.right ! null)queue.add(node.right);}res.add(temp);// 记得下层换顺序了leftToRight !leftToRight;}return res;}他人解法2dfs其实也可以看做上面 bfs 的递归版本不过主要难在入参中的当前遍历层 level 可能想不到 level 不仅可以代替 leftToRight 判断存放节点值的顺序还能根据 level 把节点值存放到对应层的 list调用递归就相当于节点入队且遍历到了下一层 具体如下 ListListInteger res new ArrayList();public ListListInteger zigzagLevelOrder(TreeNode root) {if(rootnull)return res;dfs(root, 0);return res;}public void dfs(TreeNode root, int level){if(rootnull)return;// 如果当前层还没 list 就先建一个if(res.size() level){ListInteger levelRes new ArrayList();res.add(levelRes);}// 第几层的值就存到第几层的 listListInteger levelRes res.get(level);// 判断存放值的顺序来存放if(level%20)levelRes.add(root.val);else levelRes.add(0, root.val);// 处理下一层dfs(root.left, level1);dfs(root.right, level1);}
