Js二叉树的基本操作_遍历，翻转，对称，深度，重建

二叉树是非常基础又非常重要的数据结构，在一些场合有着非常重要的作用。掌握二叉树对编写高质量代码、减少代码量有很大的帮助！非常适合计算机处理数据，所以对于程序员来说掌握二叉树是非常有必要的。

二叉树是什么？

二叉树是一种特殊的树，有以下两个特征：

二叉树的每个结点的度都不大于2；
二叉树每个结点的孩子结点次序不能任意颠倒。

为什么使用二叉树？

二叉树的前序遍历可以用来显示目录结构等；中序遍历可以实现表达式树，在编译器底层很有用；后序遍历可以用来实现计算目录内的文件及其信息等。二叉树是非常重要的数据结构，其中二叉树的遍历要使用到栈和队列还有递归等，很多其它数据结构也都是基于二叉树的基础演变而来的。熟练使用二叉树在很多时候可以提升程序的运行效率，减少代码量，使程序更易读。

二叉树不仅是一种数据结构，也是一种编程思想。学好二叉树是程序员进阶的一个必然进程。

JavaScript中的二叉树

在 JavaScript 中常用Object来实现二叉树，如上图二叉树可表示为：

var tree = {
    val: 1,
    left: {
        val: 2,
        left: {
            val: 4,
            left: null,
            right: null,
        },
        right: {
            val: 5,
            left: {
                val: 8,
                left: null,
                right: null,
            },
            right: {
                val: 9,
                left: null,
                right: null,
            },
        },
    },
    right: {
        val: 3,
        left: {
            val: 6,
            left: null,
            right: null,
        },
        right: {
            val: 7,
            left: null,
            right: null,
        },
    },
};

二叉树的先序遍历

1、访问根节点
2、对根节点的左子树进行先序遍历
3、对根节点的右子树进行先序遍历

递归版：递归先序遍历：根 - 左 - 右

const preorderTraversal = root => {
    const res = [];
    const preOrder = root => {
        if (!root) return;
        res.push(root.val); // 根
        preOrder(root.left); // 左
        preOrder(root.right); // 右
    };
    preOrder(root);
    return res;
};

非递归版：

const preorderTraversal = root => {
    if (!root) return [];
    const res = [];
    const stack = [root];
    while (stack.length) {
        // n是栈顶元素，栈顶元素出栈
        const n = stack.pop();
        // 访问栈顶元素
        res.push(n.val);
        // 栈顶左节点入栈
        n.right && stack.push(n.right);
        // 栈顶右节点入栈
        n.left && stack.push(n.left);
    }
    return res;
};

二叉树的中序遍历

1、对根节点的左子树进行先序遍历
2、访问根节点
3、对根节点的右子树进行先序遍历

递归版：递归中序遍历：左-根-右

const inorderTraversal = root => {
    const res = [];
    const inOrder = root => {
        if (!root) return;
        inOrder(root.left); // 左
        res.push(root.val); // 根
        inOrder(root.right); // 右
    };
    inOrder(root);
    return res;
};

非递归版：

const inorderTraversal = root => {
    if (!root) return [];
    const res = [];
    const stack = [];
    let p = root;
    while (stack.length || p) {
        while (p) {
            stack.push(p);
            p = p.left;
        }
        const n = stack.pop();
        res.push(n.val);
        p = n.right;
    }
    return res;
};

二叉树的后序遍历

1、对根节点的左子树进行先序遍历
2、对根节点的右子树进行先序遍历
3、访问根节点

递归版：递归后序遍历：左-右-根

const postorderTraversal = root => {
    const res = [];
    const postOrder = root => {
        if (!root) return;
        postOrder(root.left); // 左
        postOrder(root.right); // 右
        res.push(root.val); // 根
    };
    postOrder(root);
    return res;
};

非递归版：

const postorderTraversal = root => {
    if (!root) return [];
    const arr = [root];
    const res = [];
    while (arr.length) {
        const n = arr.pop();
        res.unshift(n.val);
        n.left && arr.push(n.left);
        n.right && arr.push(n.right);
    }
    return res;
};

二叉树的翻转

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

（1）就是将根节点和所有子节点的左右子树进行交换；
（2）根节点：树的最顶端的节点，每颗树只有一个根节点；
（3）子节点：除了根节点，连接有节点的节点。

const reverseTree=(root)=>{
	if (root !== null) {
		[root.left, root.right] = [root.right, root.left]
		reverseTree(root.left)
		reverseTree(root.right)
	}
}

二叉树是否完全对称

实现思路:

1、判断根节点相同
2、左子树的右节点和右子树的左节点相同
3、右子树的左节点和左子树的右节点相同

const isSymmetrical=(root)=>{
  return isSymmetricalTree(root, root);
}
const isSymmetricalTree=(node1, node2)=>{
  if (!node1 && !node2) {//判断两个节点都是否为空
    return true;
  }
  if (!node1 || !node2) { //判断两个节点是否存在一个为空
    return false;
  }
  if (node1.val != node2.val) { //判断两个节点是否相同
    return false;
  }
  return isSymmetricalTree(node1.left, node2.right) && isSymmetricalTree(node1.right, node2.left);
}

二叉树的深度

从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。解题思路：

当树为空，深度为0；
当树不为空，深度为左右子树中深度的最大值，加上这个节点本身所占的层数（1）。

const deep=(root)=>{
    if (!root) return 0;
    return Math.max(deep(root.left), deep(root.right)) + 1
}

二叉树的重建

本题是leetcode的剑指offer07题。题目给出了一个二叉树的前序遍历和中序遍历数组，前序遍历数组第一个值即为二叉树根节点的值。

得到了根节点的值，就可以在中序遍历数组中循环进行比较，当有 inorder[i] === rootVal 时，则该 i 左侧子数组为该二叉树根节点的左子树的中序遍历数组，同理该 i 的右侧子数组为其右子树的中序遍历数组。

思路：

递归，通过重建节点的左子树和右子树，实现对整个二叉树的重建，抓住前序遍历是’根左右‘，中序遍历是’左根右‘的特性，更新需要传给函数的前序遍历和中序遍历。

const buildTree = (preorder, inorder) =>{
    if (!preorder.length || !inorder.length) return null
    const root = preorder[0]
    const i = inorder.indexOf(root)
    const node = {
        val: root,
        left: buildTree(preorder.slice(1, i + 1), inorder.slice(0, i)),
        right: buildTree(preorder.slice(i + 1), inorder.slice(i + 1)),
    }
    return node
};

测试：

let preorder=[3,9,20,15,7] //前序遍历数组
let inorder=[9,3,15,20,7] //中序遍历数组
console.log(buildTree(preorder,inorder))

链接: https://www.fly63.com/article/detial/12306