从零学算法103

2023-12-28 17:46:17

103.给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:[[3],[20,9],[15,7]]
示例 2:
输入:root = [1]
输出:[[1]]
示例 3:
输入:root = []
输出:[]

  • 我的原始人解法:层序遍历,每次处理一遍从左到右的和从右到左的遍历,可以直接略过不看
  •   public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
          List<List<Integer>> res = new ArrayList<>();
          if(root==null)return res;
          Stack<TreeNode> stack = new Stack<>();
          stack.push(root);
          while(!stack.isEmpty()){
              List<Integer> temp = new ArrayList<>();
              Stack<TreeNode> tempStack = new Stack<>();
              // 从左到右遍历节点
              // stack 从左到右存节点,下面的遍历取的时候就相当于从右到左遍历
              for(int i=stack.size();i>0;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);
              }
              stack=tempStack;
              tempStack = new Stack<>();
              res.add(temp);
              temp = new ArrayList<>();
              // 从右到左遍历节点,因为上面是用 stack 从左到右存的
              // stack 从右到左存节点,下一轮的遍历取的时候就相当于从左到右遍历
              for(int i=stack.size();i>0;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);
              }
              stack=tempStack;
              // 如果到这已经遍历完了就不用加了
              if(temp.size()>0)res.add(temp);
          }
          return res;
      }
    
  • 他人解法1:层序遍历,用一个变量记录是从左到右还是从右到左存放当前层的值,这样每次遍历都从左到右放节点即可,具体看代码
  •   public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
          List<List<Integer>> res = new ArrayList<>();
          if(root==null)return res;
          boolean leftToRight = true;
          Queue<TreeNode> queue = new LinkedList<>();
          queue.add(root);
          while(!queue.isEmpty()){
              List<Integer> temp = new ArrayList<>();
              for(int i=queue.size();i>0;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;
      }
    
  • 他人解法2:dfs,其实也可以看做上面 bfs 的递归版本,不过主要难在入参中的当前遍历层 level 可能想不到, level 不仅可以代替 leftToRight 判断存放节点值的顺序,还能根据 level 把节点值存放到对应层的 list,调用递归就相当于节点入队且遍历到了下一层, 具体如下
  •   List<List<Integer>> res = new ArrayList<>();
      public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
          if(root==null)return res;
          dfs(root, 0);
          return res;
      }
      public void dfs(TreeNode root, int level){
          if(root==null)return;
          // 如果当前层还没 list 就先建一个
          if(res.size() <= level){
              List<Integer> levelRes = new ArrayList<>();
              res.add(levelRes);
          }
      	// 第几层的值就存到第几层的 list
          List<Integer> levelRes = res.get(level);
          // 判断存放值的顺序来存放
          if(level%2==0)levelRes.add(root.val);
          else levelRes.add(0, root.val);
      	// 处理下一层
          dfs(root.left, level+1);
          dfs(root.right, level+1);
      }
    

文章来源:https://blog.csdn.net/m0_53256503/article/details/135270062
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。