广度优先搜索算法 bfs all in one-编程思维

广度优先搜索算法 BFS All In One

Breadth-First Search / BFS

BFS / 广度优先搜索 / 广度优先遍历 / 按层次遍历树

应用场景

  • 二叉树层次遍历

  • 最优路径

...

demos

LeetCode

"use strict";

/**
 *
 * @author xgqfrms
 * @license MIT
 * @copyright xgqfrms
 * @created 2023-01-31
 * @modified
 *
 * @description 2196. Create Binary Tree From Descriptions
 * @description 2196. 根据描述创建二叉树
 * @difficulty Medium
 * @ime_complexity O(n)
 * @space_complexity O(n)
 * @augments
 * @example
 * @link https://leetcode.com/problems/create-binary-tree-from-descriptions/
 * @link https://leetcode.cn/problems/create-binary-tree-from-descriptions/
 * @solutions
 *
 * @best_solutions
 *
 */

export {};

const log = console.log;

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val === undefined ? 0 : val);
    this.left = (left === undefined ? null : left);
    this.right = (right === undefined ? null : right);
  }
}

// [parent, child, isLeft]
// isLefti == 1,true
// isLefti == 0, false

const findRoot = (nodes) => {
  if(nodes.length === 1) {
    return nodes[0][0];
  } else {
    const parents: number[] = [];
    const childs: number[] = [];
    // const parents = [];
    // const childs = [];
    for(let node of nodes) {
      const [parent, child] = node;
      parents.push(parent);
      childs.push(child);
    }
    for(let node of nodes) {
      const [parent, child] = node;
      if(!childs.includes(parent)) {
        return parent;
      }
    }
  }
}

/*

findRoot([[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]])
// 50
findRoot([[1,2,1],[2,3,0],[3,4,1]]);
// 1
 */


/*

[[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]

[50,20,80,15,17,19]

*/

// DFS 深度优先搜索 / 深度优先遍历
function dfs(root, nodes) {
  const childs = nodes.filter(item => item[0] === root.val);
  for(let node of childs) {
    const [parent, child, isLeft] = node;
    if(isLeft) {
      root.left = new TreeNode(child);
      dfs(root.left, nodes);
    } else {
      root.right = new TreeNode(child);
      dfs(root.right, nodes);
    }
  }
}

function createBinaryTree(descriptions: number[][]): TreeNode | null {
  const rootValue = findRoot(descriptions);
  const root = new TreeNode(rootValue);
  dfs(root, descriptions);
  return root;
};


// 按层次遍历树,BFS 广度优先搜索/遍历
function bfs(root, arr) {
  if(root === null) {
    return;
  }
  // 去重
  if(!arr.includes(root.val)) {
    arr.push(root.val)
  }
  // 先同层遍历
  if(root.left !== null && root.left.val) {
    arr.push(root.left.val)
  }
  if(root.right !== null && root.right.val) {
    arr.push(root.right.val)
  }
  // 后递归深度遍历
  if(root.left !== null) {
    bfs(root.left, arr)
  }
  if(root.right !== null) {
    bfs(root.right, arr)
  }
}

function getBinaryTreeValues(root: TreeNode | null) {
  const arr = [];
  // 按层次遍历树,BFS 广度优先搜索/遍历
  bfs(root, arr);
  return arr;
};


/*


Constraints:

1 <= descriptions.length <= 104
descriptions[i].length == 3
1 <= parenti, childi <= 105
0 <= isLefti <= 1
The binary tree described by descriptions is valid.

*/


// 测试用例 test cases
const testCases = [
  {
    input: [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]],
    result: [50,20,80,15,17,19],
    desc: 'value equal to [50,20,80,15,17,19]',
  },
  {
    input: [[1,2,1],[2,3,0],[3,4,1]],
    result: [1,2,null,null,3,4],
    desc: 'value equal to [1,2,null,null,3,4]',
  },
];

for (const [i, testCase] of testCases.entries()) {
  const result = createBinaryTree(testCase.input);
  const values = getBinaryTreeValues(result);
  const nums = testCase.result.filter(i => i !== null);
  log(`values =`, values);
  log(`nums =`, nums);
  log(`test case ${i} result: `, JSON.stringify(values) === JSON.stringify(nums) ? `✅ passed` : `❌ failed`);
  // log(`test case ${i} result: `, JSON.stringify(values) === JSON.stringify(nums) ? `✅ passed` : `❌ failed`, result);
}

/*

$ npx ts-node ./2196\ create-binary-tree-from-descriptions.ts

*/

代码优化

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

// [parent, child, isLeft]
// isLefti == 1,true
// isLefti == 0, false

const findRoot = (nodes: number[][]): number => {
  if(nodes.length === 1) {
    return nodes[0][0];
  } else {
    const parents = [];
    const childs = [];
    for(let node of nodes) {
      const [parent, child] = node;
      parents.push(parent);
      childs.push(child);
    }
    for(let node of nodes) {
      const [parent, child] = node;
      if(!childs.includes(parent)) {
        return parent;
      }
    }
  }
}

/* 

findRoot([[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]])
// 50
findRoot([[1,2,1],[2,3,0],[3,4,1]]);
// 1
 */


function dfs(root: TreeNode | null, nodes: number[][]): void {
  const childs = nodes.filter(item => item[0] === root.val);
  for(let node of childs) {
    // const [parent, child, isLeft] = node;
    const [_, child, isLeft] = node;
    if(isLeft) {
      root.left = new TreeNode(child);
      dfs(root.left, nodes);
    } else {
      root.right = new TreeNode(child);
      dfs(root.right, nodes);
    }
  }
}

function createBinaryTree(descriptions: number[][]): TreeNode | null {
  const rootValue = findRoot(descriptions);
  let root = new TreeNode(rootValue);
  dfs(root, descriptions);
  return root;
};


https://leetcode.com/problems/create-binary-tree-from-descriptions/

https://leetcode.cn/problems/create-binary-tree-from-descriptions/

(🐞 反爬虫测试!打击盗版⚠️)如果你看到这个信息, 说明这是一篇剽窃的文章,请访问 https://www.cnblogs.com/xgqfrms/ 查看原创文章!

refs

https://www.cnblogs.com/xgqfrms/p/13850733.html

https://zh.wikipedia.org/zh-hans/广度优先搜索



©xgqfrms 2012-2021

www.cnblogs.com/xgqfrms 发布文章使用:只允许注册用户才可以访问!

原创文章,版权所有©️xgqfrms, 禁止转载 🈲️,侵权必究⚠️!


版权声明:本文版权归作者所有,遵循 CC 4.0 BY-SA 许可协议, 转载请注明原文链接
https://www.cnblogs.com/xgqfrms/p/17082919.html

【leetcode哈希表#3】快乐数(set)-编程思维

快乐数 力扣题目链接(opens new window) 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为 1,那么这个数就是快乐数。 如果 n 是快乐数

个人文章-编程思维

文章内容整理自【博学谷狂野架构师】索引(index)是帮助MySQL高效获取数据的数据结构(有序)。在数据之外,数据库系统还维护着满足 特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据, 这样就可以在这些数据结构 上实现高级查找算法,这种数据结构就是索引。优缺点:优点:提高数据检索效率,降低数据库的IO成

小白科普丨何为树、二叉树和森林?-编程思维

摘要:本文为大家带来树、二叉树和森林的表示及如何进行相互转换。 本文分享自华为云社区《树、二叉树和森林的表示及相互转换》,作者:1+1=王。 树的基本概念 树的定义:树是n(n >= 0)个节点的==有限==集。当n=0是,称为空树。 树的特点: (1)树的根没有前驱,除根外的其他节点有且仅有一个前驱;(2)每