数据结构-树

树定义

树的深度与广度优先遍历

深度优先遍历

// 树
const tree = {
  val: 'a',
  children: [
    {
      val: 'b',
      children: [
        {
          val: 'd',
          children: [
          ]
        },
        {
          val: 'e',
          children: [
          ]
        }
      ]
    },
    {
      val: 'c',
      children: [
        {
          val: 'f',
          children: [
          ]
        },
        {
          val: 'g',
          children: [
          ]
        }
      ]
    }
  ]
}
// 深度优先遍历
const dfs = (root) => {
  console.log(root.val);
  root.children.forEach( dfs )
}

dfs(tree);

// 调试结果 a b d e c f g

总结： 采用递归方法

广度优先遍历

// 树
const tree = {
  val: 'a',
  children: [
    {
      val: 'b',
      children: [
        {
          val: 'd',
          children: [
          ]
        },
        {
          val: 'e',
          children: [
          ]
        }
      ]
    },
    {
      val: 'c',
      children: [
        {
          val: 'f',
          children: [
          ]
        },
        {
          val: 'g',
          children: [
          ]
        }
      ]
    }
  ]
}

// 广度优先遍历
const bfs = (root) => {
  const q = [root]; // 根节点入队
  while (q.length > 0){   // 只要队不为空则继续循环
    const n = q.shift();  // 队头出队并访问    
    console.log(n.val);
    n.children.forEach(child => {
      q.push(child);  // 队头的children挨个入队
    })

  }
}

bfs(tree);
// 调试结果 a b c d e f g

二叉树的先中后序遍历（递归版）

// bt.js// 二叉树
const bt = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 3,
      left: null,
      right: null
    },
    right: {
      val: 4,
      left: {
        val: 5,
        left: null,
        right: null
      },
      right: null
    }
  },
  right: {
    val: 6,
    left: null,
    right: {
      val: 7,
      left: null,
      right: null
    }
  }
}

module.exports = bt;

先序遍历

先序遍历算法口诀

// preorder.js
const bt = require('./bt');

// 前序遍历   根->左->右
const preorder = (root) => {
  if(!root) return	// 防止报错 为空则返回
  console.log(root.val);	// 根
  preorder(root.left);		// 左子树
  preorder(root.right);		// 右子树
}

preorder(bt); // 输出结果 1 2 3 4 5 6 7

中序遍历

中序遍历算法口诀

// 中序遍历		左->根->右
const inorder = (root) => {
  if(!root) return 
  inorder(root.left);
  console.log(root.val);
  inorder(root.right);
}
inorder(bt); // 输出结果 3 2 5 4 1 6 7

后序遍历

后序遍历算法口诀

// 后序遍历		左->右->根
const postorder = (root) => {
  if(!root) return
  postorder(root.left);
  postorder(root.right);
  console.log(root.val);
}
postorder(bt); // 输出结果 3 5 4 2 7 6 1

二叉树的先中后序遍历（非递归版）

先序遍历

// preorder.js
const bt = require('./bt');

/* 递归版 */

// // 前序遍历   根->左->右
// const preorder = (root) => {
//   if(!root) return	// 防止报错 为空则返回
//   console.log(root.val);	// 根
//   preorder(root.left);		// 左子树
//   preorder(root.right);		// 右子树
// }

// preorder(bt); // 输出结果 1 2 3 4 5 6 7

/* 非递归版 */

// 前序遍历   根->左->右
const preorder = (root) => {
  if(!root) return	// 防止报错 为空则返回
  const stack = [root];
  while(stack.length){
    const n = stack.pop();
    console.log(n.val);
    if(n.right) stack.push(n.right);  // 因栈的结构为后进先出，要先访问left则需要反一下
    if(n.left) stack.push(n.left);
  }
}

preorder(bt); // 输出结果 1 2 3 4 5 6 7

中序遍历

const bt = require('./bt');

/* 递归版 */

// // 中序遍历		左->根->右
// const inorder = (root) => {
//   if(!root) return 
//   inorder(root.left);
//   console.log(root.val);
//   inorder(root.right);
// }

// inorder(bt); // 输出结果 3 2 5 4 1 6 7

/* 非递归版 */

// 中序遍历
const inorder = (root) => {
  if(!root) return 
  const stack = [];
  let p = root;   // 声明一个指针
  while(stack.length || p){
    while(p){
      stack.push(p);
      p = p.left;   // 指针不断指向左节点
    }
    const n = stack.pop();
    console.log(n.val);
    p = n.right;    // 指针指向右节点
  }
  
}

inorder(bt); // 输出结果 3 2 5 4 1 6 7

后序遍历

const bt = require('./bt');

/* 递归版 */

// // 后序遍历   左->右->根
// const postorder = (root) => {
//   if(!root) return
//   postorder(root.left);
//   postorder(root.right);
//   console.log(root.val);
// }
// postorder(bt);    // 输出结果 3 5 4 2 7 6 1

/* 非递归版 */
// 将后续遍历倒置，用前序遍历的逻辑，用栈的特性倒过来

// 后序遍历   左->右->根
const postorder = (root) => {
  if(!root) return
  const outputStack = [];
  const stack = [root];
  while(stack.length){
    const n = stack.pop();
    outputStack.push(n);
    if(n.left) stack.push(n.left);
    if(n.right) stack.push(n.right);
  } 
  while(outputStack.length){
    const n = outputStack.pop();
    console.log(n.val);
  }
}
postorder(bt);    // 输出结果 3 5 4 2 7 6 1

刷题

LeetCode: 104. 二叉树的最大深度

题目描述

解题思路

解题步骤

Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    let res = 0;
    const dfs = (n, l) => {
        if(!n) return
        // console.log(n.val, l);
        if(!n.left && !n.right){    // 在叶子节点处进行判断最大层级
            res = Math.max(res, l);
        }
        dfs(n.left, l + 1);
        dfs(n.right, l + 1);
    }
    dfs(root, 1);
    return res;
};

时间复杂度 空间复杂度分析

• 因其中不断迭代遍历，所以时间复杂度为O(n)
• 因隐含有栈，所以空间复杂度 最差为都分布在一个节点上往下延申为O(n)， 最好为均匀分布为Olog(n)

LeetCode: 111. 二叉树的最小深度

题目描述

解题思路

解题步骤

Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    if(!root) return 0;
    const q = [[root, 1]];	// 新建一个队列，将包含根节点和层级的数组入队
    while(q.length){
        const [n, l] = q.shift();	// 将队头出队并访问
        // console.log(n.val, l);
        if(!n.left && !n.right){	// 若当前节点为叶子节点则直接返回层级
            return l;	
        }
        if(n.left) q.push([n.left, l+1]);	// 若有左子节点 将其入队
        if(n.right) q.push([n.right, l+1]);	// 若有右子节点 将其入队
    }
};

时间复杂度 空间复杂度分析

• 因最坏情况要遍历每个节点，所以时间复杂度为O(n)， n为节点数量
• 因队列有可能会装满树的节点，所以空间复杂度为O(n)， n为节点数量

LeetCode: 102. 二叉树的层序遍历

题目描述

解题思路

解题步骤

基本的广度优先遍历代码

增加层级的广度优先遍历代码（其中level是节点的层级）

Code1

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(!root) return []     // 首先对极端情况进行判断
    const q = [[root, 0]];
    const res = [];
    while(q.length){
        const [n, level] = q.shift();
        // console.log(n.val, level);
        if(!res[level]){    // 如果根节点数组没有值就将值放进去
            res.push([n.val]);
        }else{      // 在有值的情况下直接在当前层级数组后面追加即可
            res[level].push([n.val]);
        }
        if(n.left) q.push([n.left, level+1]);
        if(n.right) q.push([n.right, level+1]);
    }
    return res;
};

Code2

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(!root) return []     // 首先对极端情况进行判断
    const q = [root];
    const res = [];
    while(q.length){
        let len = q.length;
        res.push([]);
        while(len--){   // 循环次数即为节点个数，保证里面都是新的，老的已被推出
            const n = q.shift();
            res[res.length - 1].push(n.val);    // 拿到最后一个数组，将该层级所有节点推入
            if(n.left) q.push(n.left);
            if(n.right) q.push(n.right);
        }
    }
    return res;
};

时间复杂度 空间复杂度分析

• 因要遍历每个节点，所以时间复杂度为O(n)
• 因有线性增长的数组，所以空间复杂度为O(n)

LeetCode: 94. 二叉树的中序遍历

题目描述

解题思路

用到中序遍历

Code（递归版）

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    /* 递归版 */
    const res = [];
    const rec = (n)=>{
        if(!n) return;
        rec(n.left);        // 左
        res.push(n.val);    // 根
        rec(n.right);       // 右
    }
    rec(root);
    return res;
};

Code（非递归版）

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    /* 非递归版 */
    const res = [];
    const stack = [];
    let p = root;
    while(stack.length || p){
        while(p){   // 将所有左节点推入栈
        stack.push(p);
        p = p.left;
        }
        const n = stack.pop();  // 访问栈顶元素
        // console.log(n.val);
        res.push(n.val);        // 将元素推入数组中 
        p = n.right;
    }

    return res;
};

时间复杂度 空间复杂度分析

• 因要遍历每个节点，所以时间复杂度为O(n)
• 因有线性增长的数组和栈，所以空间复杂度为O(n)

LeetCode: 112. 路径总和

题目描述

解题思路

解题步骤

Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function(root, targetSum) {
    if(!root) return false;     // 1. 极端条件
    let res = false;    // 5. 声明一个变量存储布尔值
    const dfs = (n, s) => {
        // console.log(n.val, s);   // 3. 验证
        if(!n.left && !n.right && s === targetSum){
            res = true;     // 4. 判断其是否为叶子节点且路径和是否满足条件
        }
        if(n.left) dfs(n.left, s + n.left.val);     // 2. 若有左节点则继续递归
        if(n.right) dfs(n.right, s + n.right.val);  // 2. 若有右节点则继续递归
    }

    dfs(root, root.val);    // 传入根节点和根节点的值
    return res; // 6. 返回res的值
};

时间复杂度 空间复杂度分析

• 因要遍历每个节点，所以时间复杂度为O(n)， n为节点数量
• 因要递归，所以空间复杂度最坏情况下为O(n)，最好情况下为Olog(n)

前端与树：遍历JSON的所有节点值

const json = {
  a: { b: { c: 1 } },
  d: [1, 2]
}

const dfs = (n, path) => {
  console.log(n, path);		// * 在此处设置断点调试
  Object.keys(n).forEach( k => {  // Object.keys(n) 可拿到孩子节点
    dfs(n[k], path.concat(k));    // concat()将数组合并并返回
  })
};

dfs(json, []);

前端与树：渲染Antd的树组件

总结