在LeetCode学习二叉树

淡淡的烟草味﹌ 2022-01-20 02:55 177阅读 0赞

## 一、二叉树 ##

### 1、概念 ###

二叉树是一种典型的树状结构，它的每个节点最多有两个子树，通常叫做“左子树”和“右子树”。当然，二叉树是一种经常用到的数据结构。

二叉树如下图所示：

### 2、遍历 ###

二叉树有多种遍历方式，最基本的是前序遍历、中序遍历以及后续遍历，除了基本遍历方式之外，还有层序遍历。

> 前序遍历：首先访问根节点，然后遍历左子树，最后遍历右子树。  
> 中序遍历：先遍历左子树，然后访问根节点，然后遍历右子树。  
> 后续遍历：先遍历左子树，然后遍历右子树，最后访问树的根节点。

看一下前序遍历：

输入: [1,null,2,3]  
    输出: [1,2,3]复制代码

/**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {number[]}
     */
    var preorderTraversal = function(root) {
        var res = [];
        function traverse (root){
            if(root){
                res.push(root.val);
                traverse(root.left);
                traverse(root.right);
            }
        }
        traverse(root);
        return res;
    };
    复制代码

中序遍历、后续遍历其实和前序遍历是类似的，只是遍历的顺序不一样。

> 层序遍历就是逐层遍历树结构

`广度优先搜索`是一种广泛运用在树或图这类数据结构中，遍历或搜索的算法。 该算法从一个根节点开始，首先访问节点本身。 然后遍历它的相邻节点，其次遍历它的二级邻节点、三级邻节点，以此类推。

**题目：**给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:

给定二叉树: `[3,9,20,null,null,15,7]`

3
       / \
      9  20
        /  \
       15   7复制代码

输出：
    [
      [3],
      [9,20],
      [15,7]
    ]复制代码

代码如下：

思路：利用递归每次遍历层级加1。

/**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {number[][]}
     */
    var levelOrder = function(root) {
       var res = [];
       var lv = 0; 
       function level(node,lv){
           if(node){
               if(!res[lv]){
                  res[lv]=[];
               }
               res[lv].push(node.val);
               lv+=1;
               level(node.left,lv);
               level(node.right,lv);
           }
       } 
       level(root,lv); 
       return res; 
    };
    复制代码

LeetCode学习地址：https://leetcode-cn.com/explore/learn/card/data-structure-binary-tree/