树的遍历

前言

树从根节点，一值向下衍生的 的数据结构，二叉树是我们所关注的重点，对于树的遍历，我一直都不着门道，今天正好有突破，所有故此记录一下

二叉树的直径

https://leetcode-cn.com/problems/diameter-of-binary-tree/

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

      1
     / \
    2   3
   / \
  4   5

返回  3, 它的长度是路径 [4,2,1,3] 或者  [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

树的遍历

用到的数据结构是二叉树，问题的求接我们先不管，先写下一个二叉树的遍历模板如下：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function (root) {
  // 这个变量存放结构
  const result = 0;
  const helper = (node) => {
    if (!node) {
      return;
    }
    helper(node.left);
    helper(node.right);
  };
};

分析题目

接下来，我们分析下这道题，首先求的是 任意两个结点路径长度中的最大值.
分解问题就是求 树中 “左树 到 右树 之间的直径”最大,如:

4-2->5

4->2->1->3

     1
    / \
   2   3
  / \
 4   5

 4-5 路径 4-2-5      直径为2
 5-2 路径 5-2        直径为1
 4-1 路径 4-2-1      直径为2
 3-4 路径 3-1-2-4    直径为3

 细心观察，我们可以观察 左子树 到右子树的路径长度为

 左子树->父节点 + 右子树->父节点=左子树->右子树

在递归的过程中，我们不断的与遍历过的两两节点，比较直径，就可以求出了问题的解

代码实现

var diameterOfBinaryTree = function (root) {
  // 这个变量存放结构
  const result = 0;
  const helper = (node) => {
    if (!node) {
      // 一般此等题目的套路，就是返回0，或者1，
      return 0;
    }
    const left = helper(node.left);
    const right = helper(node.right);

    //
    result = Math.max(result, left + right);

    // 返回 父节点下 的某点 到父节点的最长路径值
    return Math.max(left, right) + 1;
  };
  helper(root);
  return result;
};

平衡二叉树

https://leetcode-cn.com/problems/balanced-binary-tree/

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点   的左右两个子树的高度差的绝对值不超过 1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

   3
  / \
  9  20
 / \
15  7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

      1
     / \
    2   2
   / \
  3   3
 / \
4   4

返回  false 。

不管三七二十一，先写下树的二叉树的遍历套路

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function (root) {
  let result = true;
  const helper = (node) => {
    if (!node) {
      return;
    }
    helper(node.left);
    helper(node.right);
  };
};

分析题目

如果 左右子树之间的到父节点距离的差值绝对值大于 1，那么就不是平衡树,

代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function (root) {
  let result = true;
  const helper = (node) => {
    if (!node) {
      return 0;
    }

    // 我们一般关注，一颗树中的最后两个节点，比较好分析
    const left = helper(node.left);

    const right = helper(node.right);

    if (Math.abs(left - right) > 1) {
      result = false;
    }
    // 然后，我们返回左 右 树中 值最大的一个并且加1,以便让上一层树比较
    return Math.max(left, right) + 1;
  };
};

小结

关于二叉树的遍历，分析最好先从树的最底层分析起，因为我们遍历树，采用的是递归 ，然后，思考递归返回的值，需不需要用到 辅助变量，返回也需要什么值