树的前、中、后、层序遍历的模板以及使用场景推荐

介绍下树的前、中、后遍历以及层序遍历，以及使用场景推荐。

• 递归式

  // 以前序举例，此例可输出二叉树的前序遍历。实际使用中可将result.add(root.val)灵活变动为其他语句。
  class Solution {
      ArrayList preOrderReverse(TreeNode root) {
          ArrayList result = new ArrayList();
          preOrder(root, result);
          return result;
      }
  
      void preOrder(TreeNode root, ArrayList result) {
          if (root == null) {
              return;
          }
          result.add(root.val);           // 注意这一句
          preOrder(root.left, result);
          preOrder(root.right, result);
      }
  }
  

• 迭代式

  // 以前序举例，使用标记法，将要处理的节点放入栈之后，紧接着放入一个空指针作为标记，下次检测到空指针直接处理。
  class Solution {
      public List preorderTraversal(TreeNode root) {
          List result = new linkedList<>();
          Stack st = new Stack<>();
          if (root != null) st.push(root);
          while (!st.empty()) {
              TreeNode node = st.peek();
              if (node != null) {
                  st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                  if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                  if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
                  st.push(node);                          // 添加中节点
                  st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                  
              } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                  st.pop();           // 将空节点弹出
                  node = st.peek();    // 重新取出栈中元素
                  st.pop();
                  result.add(node.val); // 根据场景，此处灵活变动。
              }
          }
          return result;
      }
  }
  

• 递归式

  // 递归+回溯，本质上是前序遍历，层序遍历更多依靠迭代实现。
  class Solution {    
      public List> resList = new ArrayList>();
  
      public List> levelOrder(TreeNode root) {
          checkFun01(root,0);
          return resList;
      }
  
      //DFS--递归方式
      public void checkFun01(TreeNode node, Integer deep) {
          if (node == null) return;
          deep++;
  
          if (resList.size() < deep) {
              //当层级增加时，list的Item也增加，利用list的索引值进行层级界定
              List item = new ArrayList();
              resList.add(item);
          }
          resList.get(deep - 1).add(node.val);
  
          checkFun01(node.left, deep);
          checkFun01(node.right, deep);
      }
  }
  

• 迭代式

  // 利用队列先进先出，达到广度优先，外循环每循环一次，相当于遍历一层；内循环逐个遍历层内节点。
  class Solution {
      public List> resList = new ArrayList>();
  
      public List> levelOrder(TreeNode root) {
          checkFun02(root);
  
          return resList;
      }
  
      //BFS--迭代方式--借助队列
      public void checkFun02(TreeNode node) {
          if (node == null) return;
          Queue que = new linkedList();
          que.offer(node);
  
          while (!que.isEmpty()) {
              List itemList = new ArrayList();
              int len = que.size();
  
              while (len > 0) {
                  TreeNode tmpNode = que.poll();
                  itemList.add(tmpNode.val);        // 根据场景，这里灵活变动。
  
                  if (tmpNode.left != null) que.offer(tmpNode.left);
                  if (tmpNode.right != null) que.offer(tmpNode.right);
                  len--;
              }
  
              resList.add(itemList);
          }
  
      }
  }
  

• 涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点。
• 求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算。
• 求二叉搜索树的属性，一定是中序了，要不白瞎了有序性了。