js Tree Data Structure & Tree Traversal Algorithm All In One

js Tree Data Structure & Tree Traversal Algorithm All In One

树的数据结构和算法

生成树和节点



树/二叉树



tree traversal / 树遍历

root = [];

  1. 前序遍历

前序遍历首先访问根节点,然后遍历左子树,最后遍历右子树。
前序遍历的结果是:1, 2, 4, 5, 7, 8, 3, 6

  1. 中序遍历

中序遍历是先遍历左子树,然后访问根节点,然后遍历右子树。
中序遍历的结果是:4, 2, 7, 5, 8, 1, 3, 6

  1. 后序遍历

后序遍历是先遍历左子树,然后遍历右子树,最后访问树的根节点。
后序遍历的结果是:4, 7, 8, 5, 2, 6, 3, 1



/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    // 二分搜索算法
    if(!nums.length) {
      return -1;
    }
    let left = 0;
    let right = nums.length -1;
    while(left <= right) {
      let mid = Math.floor((left + right) / 2);
      if(nums[mid] === target) {
        return mid;
      }
      if(nums[mid] > target) {
        right = mid - 1;
      }
      if(nums[mid] < target) {
        left = mid + 1;
      }
    }
    return -1;
};

demo



https://leetcode-cn.com/study-plan/data-structures/

https://leetcode.com/explore/interview/

https://leetcode.com/explore/featured/

https://leetcode.com/explore/learn/card/binary-search/

refs

https://githubhelp.com/loiane/javascript-datastructures-algorithms

https://github.com/loiane/javascript-datastructures-algorithms

https://github.com/loiane/javascript-datastructures-algorithms/tree/main/test/js

https://github.com/loiane/javascript-datastructures-algorithms/tree/main/test/ts

https://github.com/loiane/javascript-datastructures-algorithms/tree/main/test/ts/data-structures



Flag Counter


©xgqfrms 2012-2020

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

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


xgqfrms

推荐这些文章:

递归 二叉树前序 中序 后序遍历

 
https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *...

Leetcode No.94 Binary Tree Inorder Traversal二叉树中序遍历(c++实现)

1. 题目
https://leetcode.com/problems/binary-tree-inorder-traversal/
2. 分析
2.1 迭代法
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> todo;//定义一个栈,先入后出
while (root != nullptr || todo.empty() == false)...

lc35. 搜索插入位置

''' 二分查找,末端边界比较明显,需要额外处理 '''class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
if len(nums) == 0:
return 0
left = 0
right = len(nums) - 1
result = 0
while left <= right:
mid = int((left + right) / 2...

[leetcode] 33. Search in Rotated Sorted Array

题目
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., ...

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案

var threeSumClosest = function(nums, target) { let ans = nums[0] + nums[1] + nums[2]; const len = nums.length; nums.sort((a, b) => a - b); // 排序 for (let i = 0; i < len ; i++) { let L = i+1; let R = len-1; while(L < R){ const sum = nums[i] + nums...

算法学习100天——2 二分查找

二分查找:

有序数组,查找指定数

class solution{
public int binarySearch(int[] nums, int target){
int left = 0;
int right = nums.legth;
while (left <= right){
// 当前数组范围内的中点
int mid = left + ((right - left) >> 1);
if(nums[mid] < target){
...

LeetCode | 面试题53 - I. 在排序数组中查找数字 I【剑指 Offer】【Python】

问题
力扣
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

限制:

0 <= 数组长度 <= 50000

注意:本题与主站 34 题相同(仅返回值不同):https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
思路
二分查找
进行两次二分查找,分别找出右边界与左边...

LeetCode-34. 在排序数组中查找元素的第一个和最后一个位置

题目来源
34. 在排序数组中查找元素的第一个和最后一个位置
题目详情
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
进阶:

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?

示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
示例...

1151 LCA in a Binary Tree (30 分)(树的遍历,LCA算法)

The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that has both U and V as descendants.
Given any two nodes in a binary tree, you are supposed to find their LCA.
Input Specification:
Each input file contains one test case. For each case, the first line gives two po...

文章标题:js Tree Data Structure & Tree Traversal Algorithm All In One
文章链接:https://www.dianjilingqu.com/50881.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>