Technical blog

IT小白的成长之旅

0%

二叉树算法

发表于 更新于 分类于

思路指南

数据结构的存储方式

其实只有两种，顺序存储（数组）和链式存储（链表），要有递归的思想，自顶而下，从抽象到具体；

队列、栈：用数组实现，要处理扩容、缩容问题；用链表实现，需要更多内存空间存储节点指针；

图：用二维数组实现，邻接矩阵，判断连通性迅速单图如果稀疏则会耗费时间；链表实现：邻接表，节省空间，但操作效率不够；

散列表：通过散列函数将键映射到一个大数组中，拉链法：链表特性，操作简单但需要额外空间存储指针；线性探查法：数组特性，以便连续寻址，不需要指针存储空间但操作复杂；

树：用数组实现：堆，完全二叉树；链表实现，正常二叉树，二叉搜索树、AVL树、红黑树、区间树、B树；

二者优缺点

数组：紧凑连续存储，可以随机访问，通过索引快速搜索，相对节省空间，但需要一次分别配够空间，若需要扩容，则重新分配空间并拷贝过去，T(n) = O(n)，且每次进行插入与删除时，必须搬移后面所有数据以保持连续，T(n) = O(N)。

链表：元素不连续，靠指针指向下一个元素的位置，故不存在数组的扩容问题；在知道前驱、后驱时操作指针插入、删除的T(n)=O(1)，但同样因为不连续从而不能根据索引计算对应元素地址，无法随机访问，同样会消耗更多存储空间。

基本操作

遍历+访问；具体为：增删改查。

线性的，以for/while迭代为代表；

1
2
3
4
5
void traverse(int[] arr) { 
    for (int i = 0; i < arr.length; i++) { 
        // 迭代访问 arr[i] 
    } 
}

链表遍历框架，兼具迭代与递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 基本的单链表节点 */ 
class ListNode { 
    int val; 
    ListNode next; 
}
void traverse(ListNode head) { 
    for (ListNode p = head; p != null; p = p.next) { 
        // 迭代访问 p.val 
    } 
}
void traverse(ListNode head) { 
    // 递归访问 head.val 
    traverse(head.next);
}

二叉树遍历框架：典型的非线性递归遍历结构

1
2
3
4
5
6
7
8
9
/* 基本的⼆叉树节点 */ 
class TreeNode { 
    int val; 
    TreeNode left, right; 
}
void traverse(TreeNode root) { 
    traverse(root.left); 
    traverse(root.right); 
}

N叉树的遍历：非线性递归

1
2
3
4
5
6
7
8
9
/* 基本的 N 叉树节点 */ 
class TreeNode { 
    int val; 
    TreeNode[] children; 
}
void traverse(TreeNode root) { 
    for (TreeNode child : root.children) 
        traverse(child);
}

N叉树的遍历可扩展为图的遍历，如何实现图的环？：用个布尔数组visited做标记。

你就会发现只要涉及递归的问题，都是树的问题；其实很多动态规划问题就是在遍历⼀棵树，你如果对树的遍历操作烂熟于心，起码知道怎么把思路转化成代码，也知道如何提取别⼈解法的核⼼思 路。再看看回溯算法，前⽂回溯算法详解⼲脆直接说了，回溯算法就是个 N 叉 树的前后序遍历问题，没有例外。

medium二叉树刷题（树的核心是递归遍历）

二叉树中序遍历

方法一：基于栈的遍历

1、如果left节点存在，就入栈，然后跳left；

2、如果left和right都不存在，则保存当前节点，然后出栈，并让left等于null；

3、如果right存在，且left不存在，则保存当前节点，然后跳right。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
// 中序遍历
const inorderTraversal = (root) => {
    let list = [];
    let stack = [];
    let node = root;
    
    while(node || stack.length) {
    // 遍历左子树
      while(node) {
          stack.push(node);
          node = node.left;
      }
        node = stack.pop();
        list.push(node.val);
        node = node.right;
    }
    return list;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const inorderTraversal = root => {
  let res = [], stack = []
  while (root || stack.length) {
    if (root.left) {
      stack.push(root)；
      root = root.left；
    } else if (!root.left && !root.right) {
      res.push(root.val)；
      root = stack.pop()；
      root && (root.left = null)；
    } else if (root.right) {
      res.push(root.val)；
      root = root.right；
    }
  }
  return res
}

方法二：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var inorderTraversal = function(root) {
    let arr = [];
    if(!root) return [];

   let nums = [root];
    //递归方法实现
    MiddleOrder(root,arr);
    return arr;
};

function MiddleOrder(root,arr){
    if(root.left){
        MiddleOrder(root.left,arr);
    }
    arr.push(root.val);
    if(root.right){
        MiddleOrder(root.right,arr);
    }
}

前序遍历二叉树

方法一：基于栈的迭代实现

首先根入栈将根节点出栈，将根节点值放入结果数组中

然后遍历左子树、右子树，因为栈是先入后出，所以，我们先右子树入栈，然后左子树入栈

继续出栈（左子树被出栈）…….

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 前序遍历
const preorderTraversal = (root) => {
    const list = [];
    const stack = [];
    let node = root;
    
    while (node || stack.length){
        while (node){
            stack.push(node.right);
            list.push(node.val);
            node = node.left;
        }
        node = stack.pop();
    }
    return list;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 前序遍历
var preorderTraversal = (root) => {
    let result = []
    var preOrderTraverseNode = (node) => {
        if(node) {
            // 先根节点
            result.push(node.val)
            // 然后遍历左子树
            preOrderTraverseNode(node.left)
            // 再遍历右子树
            preOrderTraverseNode(node.right)
        }
    }
    preOrderTraverseNode(root)
    return result
};

后序遍历二叉树

按照左子树-根-右子树的方式，将其转换成迭代方式。

思路：每到一个节点 A，因为根要最后访问，将其入栈。然后遍历左子树，遍历右子树，最后返回到 A。

但是出现一个问题，无法区分是从左子树返回，还是从右子树返回。

因此，给 A 节点附加一个标记T。在访问其右子树前，T 置为 True。之后子树返回时，当 T 为 True表示从右子树返回，否则从左子树返回。

当 T 为 false 时，表示 A 的左子树遍历完，还要访问右子树。

同时，当 T 为 True 时，表示 A 的两棵子树都遍历过了，要访问 A 了。并且在 A 访问完后，A 这棵子树都访问完成了。

1, 先遍历左节点, 当遍历到末尾节点时, 记录值

2, 然后跳回上一层节点, 顺便让left等于null

3, 再遍历右节点, 同样是遍历到末尾节点时, 记录值

4, 第二次返回时, 让右节点等于null

通过这种人为的方式，不断创造末尾节点值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const postorderTraversal = root => {
  let res = [], stack = [];
  while (root || stack.length) {
    if (root.left) {
      stack.push(root);
      root = root.left;
    } 
    else if (root.right) {
      stack.push(root);
      root = root.right;
    } 
    else {
      res.push(root.val);
      root = stack.pop();
      if (root && root.left) root.left = null;
      else if (root && root.right) root.right = null;
    }
  }
  return res;
}

不同的二叉搜索树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

思路：动态规划；为了构建一颗二叉搜索树，可以遍历每一个数字i,将其作为树根，并将1…i-1作为左子树，i+1…n作为右子树，接着可以按照同样方式递归构建左右子树。原问题可以分成规模较小的两个子问题，且解可以复用，因此用动态规划处理。

具体步骤：题目要求是计算不同二叉搜索树的个数。为此，我们可以定义两个函数：G(n): 长度为 n 的序列能构成的不同二叉搜索树的个数。F(i, n): 以 i 为根、序列长度为 n 的不同二叉搜索树个数 (1 \leq i \leq n)(1≤i≤n)。可见，G(n) 是我们求解需要的函数。

动态规划问题的关键在于构建状态转移方程。

1
2
3
4
5
6
7
8
9
10
11
12
var numTrees = function(n) {
    const G = new Array(n + 1).fill(0);
    G[0] = 1;
    G[1] = 1;

    for (let i = 2; i <= n; ++i) {
        for (let j = 1; j <= i; ++j) {
            G[i] += G[j - 1] * G[i - j];
        }
    }
    return G[n];
};

在本题目的扩展下，如果要求生成所有由1-n节点所组成的二叉搜索树。

和二叉搜索树一的解法不同，一的目的是求数量，而这道题是求具体的解，所以不能从树的规律来简化；利用树的递归特性，采用DFS来递归求解；

n个数组成的二叉树，分为分别以1,2,3…,n为顶点的树；以i为例：f[i]的左边树就是1到i-1个数组成的二叉搜索树，因为左边的节点都比顶点小；f[i]的右边子树就是[i+1]到n的数组成的二叉搜索树，因为右边的节点都比顶点大；左右两侧都是树的数组；组合之后，f[i]的数组组合就得到了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * 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 {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function (n) {
    if (n == 0) return [];
    function getTree(s, e) {
        if (s > e) return [null];
        if (s == e) return [new TreeNode(s)];
        var tree = [];
        var i = s;
        while (i <= e) {
            var lefts = getTree(s, i - 1), rights = getTree(i + 1, e);
            while (lefts.length) {
                var left = lefts.pop(), j = 0;
                while (j < rights.length) {
                    var right = rights[j];
                    j++;
                    var node = new TreeNode(i);
                    node.left = left;
                    node.right = right;
                    tree.push(node);
                }
            }
            i++;
        }
        return tree;
    }
    return getTree(1, n);
};

从构建1棵树到构建n棵树，该递归思路其实清晰可见。

验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：1、节点的左子树只包含小于当前节点的数。2、节点的右子树只包含大于当前节点的数。3、所有左子树和右子树自身必须也是二叉搜索树。

方法一：设计一个递归函数来判断，函数表示考虑以root为跟的子树，其子树所有节点是否都在（l,r）的范围内。不在则直接返回，在的话则继续递归调用其左右子树是否满足。

1
2
3
4
5
6
7
8
const helper = (root, lower, upper)=>{
    if (root == null) return ture;
    if (root.val <= lower || root.val >= upper) return false;
    return helper(root.left, lower, root.val) && helper(root.right, root.val, upper);
}
var isValidBST = function(root) {
    return helper(root, -Infinity, Infinity);
};

方法二：中序遍历，二叉搜索树的中序遍历结果一定是升序序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var isValidBST = function(root) {
    let stack = [];
    let inorder = -Infinity;

    while (stack.length || root !== null) {
        while (root !== null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
        if (root.val <= inorder) return false;
        inorder = root.val;
        root = root.right;
    }
    return true;
};

对称二叉树

验证一个二叉树是否对称

方法一：递归；左子树和右子树镜像对称则这个树是对称的，1、根节点的值相同；2、一个树的右子树跟另一个树的左子树镜像对称。其实本质跟二叉树相等的递归一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const isSymmetric = (root) => {
  const check = (left, right) => { 
    if (left == null && right == null) return true;
    if (left && right) {
      return left.val == right.val &&
        check(left.left, right.right) &&
        check(left.right, right.left);
    }
    return false;
  };

  if (root) {
    return check(root.left, root.right);
  } else {
    return true;
  }
};

方法二：BFS广度遍历法；入队列的顺序：1、左子树的左子树，右子树的右子树；2、左子树的右子树，右子树的左子树；出队列的时候，检查两两是否对称。

JS中array类型提供了pop()和push()方法来模仿栈这个数据结构的方法；push()方法接受任意数量的参数，并将其逐个添加到数组尾部，并返回修改后数组的长度；pop()方法则从数组末尾溢出最后一项，减少数组的length值，然后返回溢出的项。

而JS用push()和shift()方法结合来模仿队列；shift()方法溢出数组中的第一项并返回该项，同时将数组长度减一；同时也提供了unshift()方法，能在数组前端添加任意项并返回新数组的长度。因此同时使用unshift()和pop()可以从相反方向模拟数列，在前端添加项，从末端移除项。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const isSymmetric = (root) => {
  if (root == null) return true;

  const leftQueue = [root.left];   // 队列存放左子树
  const rightQueue = [root.right]; // 队列存放右子树

  while (leftQueue.length && rightQueue.length) {
    const left = leftQueue.shift();
    const right = rightQueue.shift();
    // 左右子树都为空，没有子节点可入列，continue
    if (left == null && right == null) {
      continue;
    }
    if ((left == null && right) || (left && right == null)) {
      return false;
    }
    if (left.val != right.val) {
      return false;
    }
    leftQueue.push(left.left);
    rightQueue.push(right.right);
    leftQueue.push(left.right);
    rightQueue.push(right.left);
  }
  // 其中一个子树还有节点没遍历，说明不对称
  if (leftQueue.length || leftQueue.length) {
    return false;
  } else {
    return true;
  }
};

方法三：利用两个栈来对递归进行模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var isSymmetric = (root) => {
  if (!root) return true
  let leftStack = [], rightStack = [] // 维护两个栈
  let curLeft = root.left             // 当前的左子树
  let curRight = root.right           // 当前的右子树
  while (curLeft || curRight || leftStack.length || rightStack.length) {
    while (curLeft) {         // 左子树存在
      leftStack.push(curLeft) // 推入leftStack栈
      curLeft = curLeft.left  // 不断将左子树入栈
    }
    while (curRight) {          // 右子树存在
      rightStack.push(curRight) // 推入rightStack栈
      curRight = curRight.right // 不断将右子树压入栈
    }
    if (leftStack.length !== rightStack.length) return false
                                // 栈的高度不相等，说明结构不对称
    curLeft = leftStack.pop()   // 栈顶节点出栈，赋给curLeft
    curRight = rightStack.pop() // 栈顶节点出栈，赋给curRight
    if (curLeft.val !== curRight.val) return false
                                // 两个栈出栈的节点值不相等 不对称
    curLeft = curLeft.right     // 考察左子树的right
    curRight = curRight.left    // 考察右子树的left
  }
  return true
}

二叉树的BFS与DFS

DFS：深度优先搜索一般使用递归的方法进行实现。

1
2
3
4
5
6
7
var dfs = (root) => {
    if (root == null){
        return ;
    }
    dfs(root.left);
    dfs(root.right);
}

BFS则是使用队列的数据结构来进行遍历；

1
2
3
4
5
6
7
8
9
10
11
12
13
var dfs = (root) => {
    var queue = [];
    queue.push(root);
    while (queue.length != 0){
        var node = queue.shift();
        if (node.left != null){
            queue.push(node.left);
        }
        if (node.right != null){
            queue.push(node.right);
        }
    }
}

递归的方法其实隐含地使用了系统的栈，不需要自己去维护数据结构；BFS这种独特的遍历方式正式其用于求解层序遍历和最短路径问题的根本原因。

层序遍历与最小路径问题

1、层序遍历；利用BFS遍历二叉树无法区分队列中的节点来自哪一层，因此需要修改下代码记录队列中节点数量n（即这一层的节点数），然后一口气处理该层n个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var dfs = (root) => {
    var queue = [], res = [], level = [];
    queue.push(root);
    while (queue.length != 0){
        var n = queue.length;
        for (var i = 0; i < n; i++){
            var node = queue.shift();
            level.push(node.val);
            if (node.left != null){
                queue.push(node.left);
            }
            if (node.right != null){
                queue.push(node.right);
            }
        }
        res.pop(level);
    }
    return res;
}

其实根据上述层序遍历的代码，要实现二叉树层序遍历的反向输出，只需要修改最后res的入队列方式即可，用unshift来代替pop。

2、最短路径问题：在树中一个节点到一个节点的路径是唯一的，但在图中可能有多条路径，找寻哪一条路径最短。在BFS中，距离源点越近的点会先被遍历到。（Dijkstra算法解决的是带权最短路径问题，而BFS解决的是无权最短路径问题）

二叉树的锯齿形层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）

思路：典型广度优先题目；广度优先通过队列处理 【深度优先用栈】

1、将一层记录在数组中 并记录数组长度找下一行所有数据将数组首位弹出 将首位的左右节点追在数组后；

2、按照记录的数组长度 将上层的结点全部弹出后 此时数组只剩下下一行结点了 此时就完成了一层的遍历；类似上题 与上题区别 每层输出反向 加个条件即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
* @return {number[][]}
 *
var zigzagLevelOrder = function(root) {
  if(root==null)
    return []
  var arr=[root]
  var res=[]
  var go=true
  while(arr.length>0){
    var n=arr.length
    var now=[]
    if(go){
      while(n-->0){
        var node=arr.shift()
        now.push(node.val)
        if(node.left!=null)arr.push(node.left)
        if(node.right!=null)arr.push(node.right)
      }
      res.push(now)
    }else{
      while(n-->0){
        var node=arr.pop()
        now.push(node.val)
        if(node.right!=null)arr.unshift(node.right)
        if(node.left!=null)arr.unshift(node.left)
      }
      res.push(now)
    }
    go=!go
  }
  return res
};

前序跟中序遍历构造二叉树

思路：构建一个二叉树需要构建三部分：root、左子树、右子树；左子树、右子树的构建，又包括：root、左子树、右子树解题关键在于定位出根节点，划分出左右子树，然后 递归 构建左右子树

具体做法：preorder 数组的第一项肯定是根节点 —— 因为前序遍历的顺序是 [根| 左|右 ][根∣左∣右]。由根节点，在 inorder [左 | 根 | 右][左∣根∣右] 中划分出左、右子树的 inorder 序列。
通过 inorder 中左右子树的节点个数，在 preorder 中确定左、右子树的 preorder 序列。得到左、右子树的 preorder 和 inorder 序列，就能递归构建左右子树。

1
2
3
4
5
6
7
8
const buildTree = (preorder, inorder) => {
  if (inorder.length == 0) return null;
  const root = new TreeNode(preorder[0]);
  const mid = inorder.indexOf(preorder[0]);
  root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid));
  root.right = buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1));
  return root;
};

优化一:字符串截取性能消耗比较大，没必要每次均将preorder、inorder切割；用两个指针表示即可，写一个接受指针的辅助函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
const buildTree = (preorder, inorder) => {
  const helper = (p_start, p_end, i_start, i_end) => {
    if (p_start > p_end) return null;
    let rootVal = preorder[p_start];    // 根节点的值
    let root = new TreeNode(rootVal);   // 根节点
    let mid = inorder.indexOf(rootVal); // 根节点在inorder的位置
    let leftNum = mid - i_start;        // 左子树的节点数
    root.left = helper(p_start + 1, p_start + leftNum, i_start, mid - 1);
    root.right = helper(p_start + leftNum + 1, p_end, mid + 1, i_end);
    return root;
  };
  return helper(0, preorder.length - 1, 0, inorder.length - 1);
};

再次优化：每次递归都要indexof寻找根节点位置，耗费性能；可提前把inorder数组元素和索引存到hash表中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const buildTree = (preorder, inorder) => {
  const map = new Map();
  for (let i = 0; i < inorder.length; i++) {
    map.set(inorder[i], i);
  }
  const helper = (p_start, p_end, i_start, i_end) => {
    if (p_start > p_end) return null;
    let rootVal = preorder[p_start];    // 根节点的值
    let root = new TreeNode(rootVal);   // 根节点
    let mid = map.get(rootVal);         // 根节点在inorder的位置
    let leftNum = mid - i_start;        // 左子树的节点数
    root.left = helper(p_start + 1, p_start + leftNum, i_start, mid - 1);
    root.right = helper(p_start + leftNum + 1, p_end, mid + 1, i_end);
    return root;
  };
  return helper(0, preorder.length - 1, 0, inorder.length - 1);
};

中序跟后序遍历构造二叉树

通常从先序序列或者后序序列开始，根据不同遍历方法的规律，选择合适的节点构造树。例如：先序序列的 第一个 节点是根节点，然后是它的左孩子，右孩子等等。后序序列的 最后一个 节点是根节点，然后是它的右孩子，左孩子等等。

从先序/后序序列中找到根节点，根据根节点将中序序列分为左子树和右子树。从中序序列中获得的信息是：如果当前子树为空（返回 None），否则继续构造子树。

创建 hashmap 存储中序序列：value -> its index 。

方法 helper 的参数是中序序列中当前子树的左右边界，该方法仅用于检查子树是否为空。下面分析 helper(in_left = 0, in_right = n - 1) 的逻辑：

1、如果 in_left > in_right，说明子树为空，返回 None。

2、选择后序遍历的最后一个节点作为根节点。

3、假设根节点在中序遍历中索引为 index。从 in_left 到 index - 1 属于左子树，从 index + 1 到 in_right 属于右子树。

4、根据后序遍历逻辑，递归创建右子树 helper(index + 1, in_right) 和左子树 helper(in_left, index - 1)。

5、返回根节点 root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var buildTree = function(inorder, postorder) {
    let p = i = postorder.length - 1;
    let build = (stop) => {
        if(inorder[i] != stop) {
            let root = new TreeNode(postorder[p--])
            root.right = build(root.val)
            i--
            root.left = build(stop)
            return root
        }
        return null
    }
    return build()
}

翻转二叉树

递归三步法：1、确定递归函数的参数和返回值；2、确定终止条件；3、确定单层递归的逻辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if (root == null) return null;
    const left = invertTree(root.left);
    const right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root;
};

将有序数组转换为二叉搜索树

该解题的本质不在于二叉搜索树和中序遍历，本质是平衡。

如何满足平衡条件：每次把一组数最中间的位置作为树的头拎起来，剩余的部分平均分两份，剩余的一个随便给左子树或右子树；

1
2
3
4
5
6
def 做一棵树（数组的哪个段落要做成树）：#这个段落用索引表示即可，与具体数字无关
    #假设这个段落叫A吧
    树的根部 = 这个段落A最中间的数字
    树的左边 = 做一棵树（这个段落A的左边部分）
    树的右边 = 做一棵树（这个段落A的右边部分）
    return 这棵树

二叉搜索树中序遍历后正好是一个递增的数组；因此，其实这个树就是我们中序遍历二叉树的结果。因此我们以和中序遍历相反的方式，从中间开始取root进行构建二叉树即可。

#可以看到整个题解只和index有关，和数组里的具体数字无关， #因为题目给出的“有序数列”帮助我们满足了“二叉搜索树”的条件。因此只需要操作index来对节点进行重新构建即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const sortedArrayToBST = (nums) => {

  const buildBST = (nums, start, end) => {
    if (start > end) {
      return null;
    }
//无符号右移>>>的操作是：丢弃右边指定位数，并左边补上0，因此等于除以2。
    const mid = (start + end) >>> 1;
    const root = new TreeNode(nums[mid]);

    root.left = buildBST(nums, start, mid - 1);
    root.right = buildBST(nums, mid + 1, end);

    return root;
  };
  
  return buildBST(nums, 0, nums.length - 1);
};

二叉树hard题目

恢复二叉搜索树

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

找到二叉搜索树中序遍历得到值序列的不满足条件的位置。本方法开辟一个新数组 \textit{nums}nums 来记录中序遍历得到的值序列，然后线性遍历找到两个位置 i和 j，并重新遍历原二叉搜索树修改对应节点的值完成修复，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
const inorder = (root, nums) => {
    if (root === null) {
        return;
    }
    inorder(root.left, nums);
    nums.push(root.val);
    inorder(root.right, nums);
}

const findTwoSwapped = (nums) => {
    const n = nums.length;
    let x = -1, y = -1;
    for (let i = 0; i < n - 1; ++i) {
        if (nums[i + 1] < nums[i]) {
            y = nums[i + 1];
            if (x === -1) {
                x = nums[i];
            }
            else break;
        }
    }
    return [x, y];
}

const recover = (r, count, x, y) => {
    if (r !== null) {
        if (r.val === x || r.val === y) {
            r.val = r.val === x ? y : x;
            if (--count === 0) {
                return;
            }
        }
        recover(r.left, count, x, y);
        recover(r.right, count, x, y);
    }
}

var recoverTree = function(root) {
    const nums = [];
    inorder(root, nums);
    const [first, second] = findTwoSwapped(nums);
    recover(root, 2, first, second); 
};
-------------本文结束感谢您的阅读-------------
坚持原创技术分享，您的支持将鼓励我继续创作！