什么是二叉树？

二叉树是一种特别的树形数据结构，它的每个节点最多只能有两个子节点，一般被称为左子节点和右子节点。这个界说十分直观，形象地描述了二叉树的形状。但是，这仅仅二叉树的外表特征。

首要，二叉树的每个节点都有一个数据元素。这个元素能够是任何类型的数据，如数字、字符乃至是其他的数据结构。这些数据元素存储在节点的左子节点和右子节点中，这使得二叉树成为一个十分灵活的数据存储方法。

其次，二叉树的性质决议了它的运用规模十分广泛。比如，咱们能够利用二叉树进行高效的搜索和排序。由于每个节点最多只有两个子节点，因而咱们能够很容易地遍历整个树，找到咱们需求的元素。此外，二叉搜索树和AVL等高级数据结构也都是在二叉树的基础上构建的。

但是，尽管二叉树有许多优点，但也尤其局限性。例如，当节点的子节点数量过多时，二叉树的搜索功率会降低。这就需求咱们在实践运用中，依据具体的需求和场景，选择最合适的数据结构。

总的来说，二叉树是一种简略而强壮的数据结构，它为咱们提供了一种有用的组织和处理数据的方法。经过深化学习和了解二叉树，能够更好地了解数据结构的原理，进一步提高咱们的编程技能。

二叉树的界说

在C 中，能够运用结构体的方法界说一个二叉树（来自LeetCode）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

在JavaScript中，能够运用函数来界说一个二叉树（来自LeetCode）：

/**
 * 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)
 * }
 */

二叉树的前、中、后序遍历指的是拜访根节点的次序。比如前序遍历是优先拜访根节点，再遍历左子树，最终遍历右子树；中序遍历则是优先遍历左子树，再拜访根节点，最终遍历右子树；同理，后序遍历是先遍历左子树，然后遍历右子树，最终拜访根节点。

二叉树的前序遍历

前序遍历的次序是：根节点->左子树->右子树。

递归完成的方法是，假如二叉树非空，则先拜访根节点，然后递归地前序遍历左子树和右子树。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        preorder(root, result);
        return result;
    }
    void preorder(TreeNode* root, vector<int> &result) {
        if (!root) return;
        result.push_back(root->val);
        preorder(root->left, result);
        preorder(root->right, result);
    }
};

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    const result = [];
    const preOrder = function(root) {
        if (!root) return;
        result.push(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }
    preOrder(root);
    return result;
};

二叉树的中序遍历

中序遍历的次序是：左子树->根节点->右子树。

递归完成的方法是，假如二叉树非空，则先递归地中序遍历左子树，然后拜访根节点，最终递归地中序遍历右子树。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        inorder(root, result);
        return result;
    }
    void inorder(TreeNode* root, vector<int> &result) {
        if (!root) return;
        inorder(root->left, result);
        result.push_back(root->val);
        inorder(root->right, result);
    }
};

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    const result = [];
    const inOrder = function(root) {
        if (!root) return;
        inOrder(root.left);
        result.push(root.val);
        inOrder(root.right);
    }
    inOrder(root);
    return result;
};

二叉树的后序遍历

后序遍历地的次序是：左子树->右子树->根节点。

递归完成的方法是，假如二叉树非空，则先递归地后序遍历左子树，然后递归地后序遍历右子树，最终拜访根节点。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        postorder(root, result);
        return result;
    }
    void postorder(TreeNode* root, vector<int> &result) {
        if (!root) return;
        postorder(root->left, result);
        postorder(root->right, result);
        result.push_back(root->val);
    }
};

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    const result = [];
    const postOrder = function(root) {
        if (!root) return;
        postOrder(root.left);
        postOrder(root.right);
        result.push(root.val);
    }
    postOrder(root);
    return result;
};

一维数组转二叉树

一维数组和二叉树是两种常见的数据结构，各有其独特的特性和用途。但是，有时咱们需求在这两种数据结构之间进行转化。

首要，咱们来了解这两种数据结构的基本概念。一维数组是一种线性的数据结构，能够经过索引快速拜访恣意元素；而二叉树则是一种层次结构的数据结构，每个节点最多有两个子节点，一般称为左子节点和右子节点。

假定咱们有一个一维数组，其中包括n个元素，能够依照以下步骤将其转化为二叉树：

  1. 创建一个空的二叉树；
  2. 从一维数组的第一个元素开始，将其作为根节点放入二叉树中；
  3. 对于一维数组中的下一个元素，假如其值小于根节点的值，则将其作为左子节点放入左子树中；不然，将其作为右子节点放入右子树中；
  4. 重复步骤3，直到处理完一维数组中的所有元素。
function TreeNode(val, left, right) {
     this.val = (val === undefined) ? 0 : val;
     this.left = (left === undefined) ? null : left;
     this.right = (right === undefined) ? null : right;
}
function buildBinaryTree(arr) {
    var root = null;
    if (!arr || arr.length === 0) return root;
    root = new TreeNode(arr[0]);
    for (var i = 1; i < arr.length; i  ) {
        insertNode(arr[i], root);
    }
    return root;
}
function insertNode(current, root) {
    if (root === null) root = { val: current, left: null, right: null };
    else if (current <= root.val) root.left = insertNode(current, root.left);
    else root.right = insertNode(current, root.right);
    return root;
}