解密二叉树：探索概念、类型与常见算法的奥秘（顺带说一下React中的reconcile）

前言

整理的关于二叉树的概念、类型和常见算法的内容非常详细，涵盖了二叉树的基本知识和常见操作。下面是文章的内容概要：

背景

• 介绍了二叉树在程序中的广泛应用，如React中的协调过程。
• 简要介绍了React中的协调过程和相关的概念。
• 补充了对二叉树的认识和学习的重要性。

二叉树概念

• 定义了二叉树作为一种数据结构，包括根节点、左子树和右子树。
• 描述了二叉树的特性，包括唯一根节点、父节点和节点间不能形成闭环的限制。

二叉树类型

• 介绍了三种常见的二叉树类型：完全二叉树、满二叉树和平衡二叉树。
• 对每种类型进行了图示和解释。

二叉树的遍历

• 介绍了三种常见的二叉树遍历方式：前序遍历、中序遍历和后序遍历。
• 对每种遍历方式进行了图示和解释。
• 提供了递归和非递归两种实现方式的代码示例。

二叉树常见算法

• 介绍了二叉搜索树的概念和操作，包括创建和搜索节点的代码示例。
• 介绍了镜像二叉树的概念和操作，包括递归和非递归两种实现方式的代码示例。

背景

二叉树作为程序的一种数据结构，应用广泛，比如React中的reconcile过程，Fiber树的调和过程。确实，在React中，Fiber树是通过child和sibling连接子节点和兄弟节点的方式来表示的，这与普通的二叉树有所不同。

在React中，reconcile过程是将虚拟DOM转化为实际DOM的过程。通过比较新旧两棵树的差异，React可以高效地更新实际DOM，而不是每次都完全重新渲染整个DOM树。这个过程中会涉及到对Fiber树的遍历和调整，确保更新只发生在需要更新的部分。

Fiber树作为一种数据结构，可以帮助React跟踪组件的状态和变化，以及进行调度和渲染。它使用链表的形式来组织组件树，使得遍历和更新变得更加高效。Fiber树的调和过程涉及到了遍历Fiber树的节点，执行副作用和收集需要更新的节点等操作，以实现高效的更新和渲染。

下面是我找的图：（很详细）

reconcile 的过程是协调fiber tree的过程，字面的意思是说让fiber tree变得更加协调，fiber tree的本质其实类似于一棵二叉树，所以整个的协调过程就是二叉树的调整过程。不过和通常的二叉树不一样的地方在于，fiber tree 是通过child 和 sibling 连接孩子节点和兄弟节点的。

在整个协调的过程，主要干了三件事情，第一件事情是在fiber tree中找到fiber node , 第二件事情是在标记有副作用的fiber node , 最后收集带有副作用的node。

无论是对于reconcile【协调】，还是面试题，有时看到二叉树这种数据结构时，很头疼难理解，但正是react reconcile 过程 使我对二叉树这种数据结构有了新的认识，所以我重新整理了二叉树的知识点，重新进行了学习。

这篇文章整理了二叉树的概念、类型与常见算法，希望对你有帮助。

二叉树概念

二叉树是n个有限元素的集合，该集合或者为空、或由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。

二叉树特性：

• 仅有唯一一个根节点，没有节点则为空树
• 除根节点外，每个节点都有并仅有唯一一个父节点
• 节点间不能形成闭环

图：

二叉树特点：

• 节点的深度 ：从根节点到该节点所经历的边的个数。
• 节点的高度 ：节点到叶节点的最长路径。

二叉树类型

二叉树类型：

• 完全二叉树
• 满二叉树
• 平衡二叉树

完全二叉树

一棵二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，第d层节点的可以小于2，并且最下层的叶节点集中在靠左的位置上。

满二叉树

所有叶节点都在最底层的完全二叉树。

一棵满二叉树必定是一棵完全二叉树，而完全二叉树不一定是满二叉树。

平衡二叉树

任何节点的两棵子树的高度差不大于1的二叉树。

对于平衡二叉树要特别注意的是，不要求非叶节点都有两个子结点，仅要求两个子树的高度差的绝对值不超过1，或者为空树。

二叉树的遍历

二叉树的遍历：

• 前序遍历
• 中序遍历
• 后序遍历

前序遍历

对于二叉树中的任意一个节点，先打印该节点，然后是它的左子树，最后右子树。

根结点 -> 左子树 -> 右子树

输入: [1,null,2,3]
   1
    \
     2
    /
   3
输出: [1,3,2]

/**
 * 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[]}
 */
let preorderTraversal  = (root) => {
   
   
    var res = [];
    dfs(root);
    function dfs(root){
   
   
        if(!root) return;
        res.push(root.val);
        dfs(root.left);
        dfs(root.right);
    }
    return res;
}

// 非递归
var preorderTraversal = function(root) {
   
   
    let res = []
    if(!root) return res;
    const stack = [root];
    let cur = null;
    while(stack.length) {
   
   
        cur = stack.pop();
        res.push(cur.val);
        cur.right && stack.push(cur.right);
        cur.left && stack.push(cur.left);
    }
    return res;
};

中序遍历

对于二叉树中的任意一个节点，先打印它的左子树，然后是该节点，最后右子树。

左子树 -> 根结点 -> 右子树

输入: [1,null,2,3]
   1
    \
     2
    /
   3
输出: [1,3,2]

//递归
function inOrder(root) {
   
   
    const res = []
    const rec = (n) => {
   
   
        if(!n) return 
        rec(n.left)
        res.push(n.val)
        rec(n.right)
    }
    rec(root)
    return res
}

//非递归
function inorderTraversal(root) {
   
   
    const res = []
    const stack = []
    while(stack.length || root) {
   
   
        if(root) {
   
   
            stack.push(root)
            root = root.left
        } else {
   
   
            const node = stack.pop()
            res.push(node.val)
            root = node.right
        }
    }
    return res
}

后序遍历

对于二叉树中的任意一个节点，先打印它的左子树，然后是右子树，最后该节点。

左子树 -> 右子树 -> 根结点

输入: [1,null,2,3]
   1
    \
     2
    /
   3
输出: [3,2,1]

//递归
function postorderTraversal(root) {
   
   
    if(!root) return []; 
    let arr =[]; 
    function preNode(root,arr){
   
   
        if(!root) return [];
        preNode(root.left,arr);
        preNode(root.right,arr);
        arr.push(root.val);
    }
    preNode(root,arr); 
    return arr
}

//非递归
function postorderTraversal(root) {
   
   
    let res = [];
    if(!root){
   
   
        return res;
    }
    let stack = [root];
    let cur;
    while(stack.length){
   
   
        cur = stack.pop(); //取出中间元素
        res.unshift(cur.val);
        cur.left && stack.push(cur.left);
        cur.right && stack.push(cur.right);
    }
    return res;
}

二叉树常见算法

二叉搜索树

又称二叉查找树、二叉排序树，其根节点的值大于其左子树中任意一个结点的值，小于其右子树中任意一结点的值，这一规则适用于二叉查找树中的每一个节点。

创建二叉树节点

function insertTree(node, val) {
   
   
    if(!node){
   
   
        node = new TreeNode();
        node.val = val;
        node.left = null;
        node.right = null;
        return true;
    }
    if(node.val == val)
        return false;
    if(node.val > val)
        return insertTree(node.left, val);
    else
        return insertTree(node.right, val)
}

搜索二叉树节点

function SearchTree(node, val) {
   
   
    if(!node)
        return null;
    if(node.val == val)
        return node;
    if(node.val > val)
        return SearchTree(node.left, val);
    else
        return SearchTree(node.right, val);
}

镜像二叉树

映射二叉树的对称节点。

例如输入：
     4
   /   \
  2     7
 / \   / \
1   3 6   9

镜像输出：
     4
   /   \
  7     2
 / \   / \
9   6 3   1

观察发现，镜像可以理解为左右子树互换，同时 其各子树的左右子树再递归互换。

//递归：自下向上换
function Mirror(root) {
   
   
    if(!root)
        return null;
    var left = Mirror(root.left);   
    var right = Mirror(root.right); 
    root.left = right;              
    root.right = left;              
    /*
      另一种写法：
      Mirror(root.left);
      Mirror(root.right);
      [root.left, root.right] = [root.right, root.left];  
    */
    return root;
}

//非递归：从上向下换
function Mirror(root) {
   
   
    if(!root)   //不加这个root为null时会报错
        return root;  
    var a = [];  //队列
    a.push(root);
    while(a.length != 0){
   
   
        var l = a.length;
        for(var i = 0; i < l; i++){
   
   
            var node = a.shift();  //压出第一个元素
            if(node.left)
                a.push(node.left);
            if(node.right)
                a.push(node.right);
            //左右指针交换
            [node.left, node.right] = [node.right, node.left];
        }
    }
    return root;
}

判断是否为镜像

function isMirror(node1, node2) {
   
   
    if(node1 == null && node2 == null)
        return true;
    if(node1 == null || node2 == null)
        return false;
    if(node1.val != node2.val)
        return false;
    return isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);
}
isMirror(root.left, root.right);

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树

• 思路

  1. 确定根结点，前序遍历的第一个结点为根节点
  2. 确定两种遍历方式的左右子树顺序
  3. 在左子树中递归步骤1和2
  4. 在右子树中递归步骤1和2
  5. 打印当前根

function reConstructBinaryTree(pre, vin) {
   
   
    // write code herepre
    if(pre.length == 0 || vin.length == 0)
        return null;
    var index = vin.indexOf(pre[0]);  //根结点在中序遍历中的位置
    var vinLeft = vin.slice(0, index);  //中序左子树
    var vinRight = vin.slice(index+1);  //中序右子树
    var preLeft = pre.slice(1, index+1);  //前序右子树
    var preRight = pre.slice(index+1);    //前序左子树
    var root = new TreeNode(pre[0]);
    root.left = reConstructBinaryTree(preLeft, vinLeft);
    root.right = reConstructBinaryTree(preRight, vinRight);
    return root;
}

二叉树深度

//递归
function depth(node) {
   
   
    if(!node)
        return 0;
    return Math.max(depth(node.left), depth(node.right))+1;
}

//非递归
function depth(root) {
   
   
    var queue = [];
    queue.push(root);
    var count = 0;
    while(queue.length != 0) {
   
   
        var l = queue.length;
        for(let i = 0; i < l; i++){
   
   
            var node = queue.shift();
            if(node.left)
                queue.push(node.left);
            if(node.right)
                queue.push(node.right);
        }
        count++;
    }
    return count;
}

二叉树结点总数

function getNodeNumber(root) {
   
   
    if (!root) return 0;
    const queqe = [root];

    let index = 0;
    while(queqe.length > 0) {
   
   
        let p = queqe.shift();
        index++;
        if (p.left) queqe.push(p.left);
        if (p.right) queqe.push(p.right);
    }

    return index;
}

叶子结点数

function getLeafNum(node) {
   
   
    if(!node)
        return 0;
    if(!node.left && !node.right)
        return 1;
    return getLeafNum(node.left)+getLeafNum(node.right);
}

层序恢复二叉树

var arr = [5,3,6,2,4,null,8,1,null,null,null,7,9]

function reconstructTree(arr) {
   
   
    if (arr.length == 0) return null;
    let root = new TreeNode(arr[0]);
    let q = [root];
    let idx = 1;

    while (q.length > 0 && idx < arr.length) {
   
   
        let cur = q.shift();
        if (arr[idx] !== null) {
   
   
            cur.left = new TreeNode(arr[idx]);
            q.push(cur.left);
        }
        idx++;
        if (arr[idx] !== null && idx < arr.length) {
   
   
            cur.right = new TreeNode(arr[idx]);
            q.push(cur.right);
        }
        idx++;
    }
    return root;
}