介绍

树是由 n（n >= 0）个结点组成的有限集合，也可以理解为：树是由根结点和若干子树构成。

  • 有且只有一个特定的结点，称为根结点。
  • 每一个元素称为结点。
  • 除根结点外，其余结点被分成 m（m >= 0）个互不相交的有限集合，而每个子集又都是一棵树（称为原树的子树）。
  • 每一个结点，可以拥有多个子树。

平时我们说的最多的是二叉树，也就是每一个结点，最多有两个子结点，也就是左右子结点，并且左右两个子结点是有顺序要求的，不可以随意颠倒。

下面为大家介绍几种二叉树：

满二叉树：每一层的结点，都完全覆盖（全部有值），也就是每一个非叶子结点，都有两个子结点。

完全二叉树：除了最后一层以外，每一层的结点数都达到最大个数，最后一层的结点，都连续并且靠左。（满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树）。

二叉查找树：任意非空结点的左子树如果不为空，则左子树的值小于根结点的值，任意非空结点的右子树如果不为空，则右子树的值大于根结点的值，任意结点的左右子树都是二叉查找树，并且结点的数值互不相等。

树的遍历

树的顺序遍历方式，一般有前序，中序，后序遍历：

  • 前序遍历：对于每一个结点，都先访问根结点（当前结点），再遍历左子树，最后比遍历右子树。
  • 中序遍历：对于每一个结点（当前结点），先遍历左子树，再访问当前结点，最后遍历右子树。
  • 后序遍历：对于每一个结点（当前结点），先遍历左子树，再遍历右子树，最后遍历当前结点。

代码实现

const preorderTraversal = (root) => {
  const res = [];
  const preOrder = (root) => {
    if (root == null) return;
    res.push(root.val);
    preOrder(root.left);
    preOrder(root.right);
  };
  preOrder(root);
  return res;
}
const inorderTraversal = (root) => {
    const res = [];
    const inorder = (root) => {
        if (root == null) {
            return;
        }
        inorder(root.left); // 先递归左子树
        res.push(root.val); // 将当前节点值推入res
        inorder(root.right); // 再递归右子树
    };
    inorder(root);
    return res;
};
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function (root) {
  let res = [];
  const postOrder = (root) => {
    if (root == null) return;
    postOrder(root.left);
    postOrder(root.right);
    res.push(root.val);
  };
  postOrder(root);
  return res;
};

层序遍历

上往下打印出二叉树的每个结点，同层结点从左至右打印，也就是按照层次来遍历。

第一反应想到的是，需要把每一层存起来，才能保证能取到下一层的元素，为了达到这个目的，我们引入了队列。

针对每一个元素（譬如从根节点开始），先把当前元素放进队列尾部，然后不断取出队列头部的元素，取出元素的时候，同时处理其左子树和右子树，将其放到队列尾部，处理直到队列为空。

总所周知，队列的特点是先进先出，也就是我们可以保证，根结点先进去，然后根结点取出来，打印根结点。同时如果根结点的左结点不为空，则将左结点放进队列，右结点如果不为空，同样放进队列中，然后又取出队列的第一个元素打印，将它的左右结点不为空的结点加到队列中，这样循环下去即可。

/**
 * 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[][]}
 */
 var levelOrder = function(root) {
    const res=[]
    if(!root){
        return  res
    }
    const queue=[]
    queue.push(root)
    while(queue.length){
        let level=[]
        let len=queue.length
        for(let i=0;i<len;i++){
            const top=queue.shift()
            level.push(top.val)
            if(top.left){
                queue.push(top.left)
            }
            if(top.right){
                queue.push(top.right)
            }
        }
        res.push(level)
    }
    return res
};

根据前序和中序遍历，构建二叉树

求解思路

前序序列中的特征是，第一个元素就是根节点，后面的元素就是左右子树的节点，确定了根节点之后，从中序遍历中，查找根节点的位置，将序列分成左右两组，左边就是左子树，右边就是右子树，查找到根结点的时候，统计了左子树上结点的数量，以及右子树上结点的数量。再用左右结点的数量，按照前序遍历序列，就可以拆出来左右子树。

代码实现

/**
 * 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[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(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
};

二叉树的最大深度

求解思路

既然输入的是一个树的根结点，也就是从根结点开始，我们就可以获取到树的所有结点，很容易想到的一种解法—递归。对于任意一个结点 node 而言，我要想知道当前 node 结点（包括当前结点）的深度，肯定得求当前结点的左子树（设为 left）的深度 leftDeepth，以及获取右子树（设为right）的深度 rightDeepth，然后求两者最大并加上 1（Max{leftDeepth，rightDeepth}+1），就是以当前结点为根节点的子树的深度。

代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
 var maxDepth = function(root) {
    if(root===null) return 0
    return Math.max(maxDepth(root.left),maxDepth(root.right))+1
};

翻转二叉树

求解思路

使用递归，直接将左子树反转，右子树反转，交换即可。值得注意的是，反转后的结果需要暂时先保存，左右两个子树都反转之后，才能赋值。

代码实现

const invertTree = (root) => {
  if (root == null) {
    // 遍历到null节点时，不用翻转，直接返回它本身
    return root;
  }
  const temp = root.left;
  root.left = root.right;
  root.right = temp;
  invertTree(root.left);
  invertTree(root.right);
  return root;
};

树的子结构

问题描述

我们都知道，树的结点都有左子树，右子树，左子树里面又有自己的左子树和右子树等等，那么我们如何判断一棵二叉树，是不是另外一棵二叉树的子树呢？（空树不是任意一个树的子结构）

求解思路

关于子树，肯定是子树上的任意节点，都能在主树上被匹配，也就是说我们需要匹配的是子树上的所有结点。那么可以先找到相同的根结点，然后递归判断左子树和右子树即可。

判断结点是不是相等时，如果子树遍历完成，则返回 true；其他情况，除非两个结构的结点都不为空且相等时，才返回 true，否则返回 false。

代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} A
 * @param {TreeNode} B
 * @return {boolean}
 */
 var isSubStructure = function(A, B) {
     if(A===null || B===null){
         return false
     }
     return isSub(A,B) ||isSubStructure(A.left,B) || isSubStructure(A.right,B)
}
function isSub(A,B){
    if(B===null){
        return true
    }
    if(A===null || A.val!=B.val){
        return false
    }
    return isSub(A.left,B.left) && isSub(A.right,B.right)
}

不同结点的最近公共祖先结点

问题描述

在一棵二叉树上的有很多结点，我们给定两个结点，找出最近的祖父结点。

我们知道，在同一棵树上的最远共同祖父结点就是根结点。譬如下面的树中，结点 4 和 5 的最近公共父结点就是 2，4 和 6 的最近公共父结点是 1。

求解思路

首先，我们从根节点开始，假设需要查找结点 m 和 n 的最近公共祖先节点。步骤如下所示：

  1. 在左、右子树中分别查找是否包含 m 或 n，如果左子树包含 m，右子树或者左子树包含 n，右子树也包含 m，那么此时的根结点就是最近公共祖先。
  2. 如果左子树包含 m 和 n，那么需要在左子树中查找，则最近公共祖先在左子树里面。
  3. 如果右子树包含 m 和 n，那么需要在右子树中查找，则最近公共祖先在右子树里面。

代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
 var lowestCommonAncestor = function(root, p, q) {
    // 1. 确定递归的函数
    const travelTree = function(root,p,q) {
        // 2. 确定递归终止条件
        if(root === null || root === p||root === q) {
            return root;
        }
        // 3. 确定递归单层逻辑
        let left = travelTree(root.left,p,q);
        let right = travelTree(root.right,p,q);
      	//如果在某一个节点的左右子树都能找到p和q说明这个节点就是公共祖先
        if(left !== null&&right !== null) {
            return root;
        }
        if(left ===null) {//如果左子树没找到就说明p，q都在右子树
            return right;
        }
        return left;//如果右子树没找到就说明p，q都在左子树
    }
   return  travelTree(root,p,q);//递归开始
};


树的路径求和

问题描述

一般而言，二叉树上的每一个结点，都存储着属于自己的数据，这个数据可以是数字，也可以是其他东西。而假设我们有一棵二叉树和一个整数，按字典顺序打印出二叉树中结点值的和为输入整数的所有路径。所谓路径，就是从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

求解思路

我们可以采用深度优先搜索的方式，枚举每一条从根节点到叶子节点的路径。当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径。

代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
 const pathSum = (root, sum) => {
    // 1. 设置结果集
    const result = [];
    const path=[]
    // 2. 深度优先搜索：root -> 树；path -> 路径；treeSum -> 当前路径和
    const recursion = (root, path, treeSum) => {
      // 2.1 终止条件
      if (!root) {
        return;
      }
  
      // 2.2 路径添加一个元素
      path.push(root.val);
  
      // 2.3 计算当前路径总和
      treeSum += root.val;
  
      // 2.4 如果没有左子树和右子树（叶子节点）
      if (!root.left && !root.right) {
        // 2.5 如果结果等于目标结果
        if (treeSum === sum) {
          result.push(path.slice());
        }
      } else {
        // 2.6 进一步递归左子树和右子树
        recursion(root.left, path, treeSum);
        recursion(root.right, path, treeSum);
      }
  
      // 2.7 回溯
      path.pop();
    };
    recursion(root, path, 0);
  
    // 3. 返回结果
    return result;
  };

判断是否为平衡二叉树

问题描述

我们都知道，平衡二叉树是一种特殊的二叉树，平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

那么我们该如何判断二叉树是否是平衡二叉树呢？平衡二叉树的左右两个子树的深度相差不超过 1，而且同时左右子树也要是平衡二叉树。

求解思路

既然要判断整棵树，也要分别判断两个子树，那么想到的肯定就是递归。判断流程大致如下：

  1. 判断根结点是否为 null，为 null 直接返回 true。
  2. 根结点如果不为 null，需要求出左子树的高度以及右子树的高度，如果两个相差大于 1，则返回 false。
  3. 如果两个子树的深度相差小于等于 1，就需要分别判断左，右子树是否为平衡树。也就是以左右两个子结点为根结点，从第 1 步开始执行。
/**
 * 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 {boolean}
 */
/**
 * 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 {boolean}
 */
var isBalanced = function(root) {
    if (!root) {
        return true
    }
    let left = maxDepth(root.left)
    let right = maxDepth(root.right)
    return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right)
};
var maxDepth = function(root) {
    if(!root) {
        return 0
    } else {
        let left =  maxDepth(root.left)
        let right =  maxDepth(root.right)
        return 1 + Math.max(left, right)
    }
};