二叉树

还在更新中。。。

---

二叉树

1. 二叉树的遍历方式

二叉树主要有两种遍历方式：

• 深度优先遍历：先往深走，遇到叶子节点再往回走。
• 广度优先遍历：一层一层的去遍历。
  进一步拓展：
• 深度优先遍历
  • 前序遍历（递归法，迭代法）
  • 中序遍历（递归法，迭代法）
  • 后序遍历（递归法，迭代法）
• 广度优先遍历
  • 层次遍历（迭代法）

前序、中序、后续对应顺序如下

代码(递归)：

var preorderTraversal = function (root) {
  let res = [];
  const dfs = function (root) {
    if (root === null) return;
    //先序遍历所以从父节点开始
    res.push(root.val);
    //递归左子树
    dfs(root.left);
    //递归右子树
    dfs(root.right);
    // 中序
    // dfs(root.left);
    // res.push(root.val);
    // dfs(root.right);
    // 后序
    // dfs(root.left);
    // dfs(root.right);
    // res.push(root.val);
  };
  //只使用一个参数 使用闭包进行存储结果
  dfs(root);
  return res;
};

代码(迭代)：

// 入栈 右 -> 左
// 出栈 中 -> 左 -> 右
前序遍历: var preorderTraversal = function (root, 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;
};

// 入栈 左 -> 右
// 出栈 左 -> 中 -> 右

中序遍历: var inorderTraversal = function (root, res = []) {
  const stack = [];
  let cur = root;
  while (stack.length || cur) {
    if (cur) {
      stack.push(cur);
      // 左
      cur = cur.left;
    } else {
      // --> 弹出 中
      cur = stack.pop();
      res.push(cur.val);
      // 右
      cur = cur.right;
    }
  }
  return res;
};

// 入栈 左 -> 右
// 出栈 中 -> 右 -> 左 结果翻转

后序遍历: var postorderTraversal = function (root, res = []) {
  if (!root) return res;
  const stack = [root];
  let cur = null;
  do {
    cur = stack.pop();
    res.push(cur.val);
    cur.left && stack.push(cur.left);
    cur.right && stack.push(cur.right);
  } while (stack.length);
  return res.reverse();
};

二叉树的最大深度

// 递归
var maxdepth = function (root) {
  //使用递归的方法 递归三部曲
  //1. 确定递归函数的参数和返回值
  const getdepth = function (node) {
    //2. 确定终止条件
    if (node === null) {
      return 0;
    }
    //3. 确定单层逻辑
    let leftdepth = getdepth(node.left);
    let rightdepth = getdepth(node.right);
    let depth = 1 + Math.max(leftdepth, rightdepth);
    return depth;
  };
  return getdepth(root);
};

// 迭代
var maxDepth = function (root) {
  if (!root) return 0;
  let count = 0;
  const queue = [root];
  while (queue.length) {
    let size = queue.length;
    /* 层数+1 */
    count++;
    while (size--) {
      let node = queue.shift();
      node.left && queue.push(node.left);
      node.right && queue.push(node.right);
    }
  }
  return count;
};

对称二叉树

var isSymmetric = function (root) {
  //使用递归遍历左右子树 递归三部曲
  // 1. 确定递归的参数 root.left root.right和返回值true false
  const compareNode = function (left, right) {
    //2. 确定终止条件 空的情况
    if (
      (left === null && right !== null) ||
      (left !== null && right === null)
    ) {
      return false;
    } else if (left === null && right === null) {
      return true;
    } else if (left.val !== right.val) {
      return false;
    }
    //3. 确定单层递归逻辑
    let outSide = compareNode(left.left, right.right);
    let inSide = compareNode(left.right, right.left);
    return outSide && inSide;
  };
  if (root === null) {
    return true;
  }
  return compareNode(root.left, root.right);
};