102.md

✏️Leetcode基础刷题之(102. Binary Tree Level Order Traversal)

2019-05-30 吴亲库里 库里的深夜食堂

---

✏️描述

给定一棵树，按照他的层次进行遍历，返回。

✏️题目实例

​

✏️题目分析

DFS和BFS都可以解,竟然已经要我们按照层打印了，那么先使用BFS，思路就是先判断树是否是空，不是空加入一个队列的结构中，如果队列不为空，取出头元素，那么当前元素表示的就是当前这一层了，所以只需要遍历这一层里的所有的元素即可，然后下一层....

✏️具体实现

      class Solution {
      
          /**
           * @param TreeNode $root
           * @return Integer[][]
           */
          function levelOrder($root) {
              if(empty($root)) return [];
              $result=[];
              $queue=[];
              array_push($queue,$root);
              while(!empty($queue)){
                  $count=count($queue);
                  $leveQueue=[];
                  for($i=0;$i<$count;$i++){
                      $node=array_shift($queue);
                      array_push($leveQueue,$node->val);
                      if($node->left) array_push($queue,$node->left);
                      if($node->right) array_push($queue,$node->right);
                  }
                  array_push($result,$leveQueue);
              }
              return $result;
          }
      }

---

如果使用DFS的话，就是一条路走到黑，然后再重新一路路的退回来再找下一路，所以这样的话，每一次我们需要记录一下当前他所在的这个点属于哪一层即可，代码用递归实现。

class Solution {

    /**
     * @param TreeNode $root
     * @return Integer[][]
     */
    function levelOrder($root) {
        if(empty($root)) return [];
        $result=[];
        $this->helper($result,$root,0);
        return $result;
    }
    function helper(&$result,$node,$level){
        if(empty($node)) return ;
        if(count($result)<$level+1){
            array_push($result,[]);
        }
        array_push($result[$level],$node->val);
        $this->helper($result,$node->left,$level+1);
        $this->helper($result,$node->right,$level+1);

    }
}

联系

​