常见树算法

[Leo-lin214]

对树数据结构常见的算法进行总结，也为了更好滴应对后面深入学习算法。

中序遍历

• 递归实现。

  答案

  
    const midMap1 = (node, result) => {
      if (node) {
        midMap1(node.left, result);
        result.push(node.val);
        midMap1(node.right, result);
      }
      return result;
    }
    

• 非递归实现。

  答案

  
    const midMap2 = node => {
      const result = [];
      const stack = [];
      let currentNode = node;
      while (currentNode || stack.length) {
        while (currentNode) {
          stack.push(currentNode);
          currentNode = currentNode.left;
        }
        currentNode = stack.pop();
        result.push(currentNode.val);
        currentNode = currentNode.right;
      }
    }
    

前序遍历

• 递归实现。

  答案

  
    const qianMap1 = (node, result) => {
      if (node) {
        result.push(node.val);
        qianMap1(node.left, result);
        qianMap1(node.right, result);
      }
      return result;
    }
    

• 非递归实现。

  答案

  
    const qianMap2 = node => {
      const result = [];
      const stack = [];
      let currentNode = node;
      while (currentNode || stack.length) {
        while (currentNode) {
          result.push(currentNode.val);
          stack.push(currentNode);
          currentNode = currentNode.left;
        }
        currentNode = stack.pop();
        currentNode = currentNode.right;
      }
    }
    

后序遍历

• 递归实现。

  答案

  
    const houMap1 = (node, result) => {
      if (node) {
        houMap1(node.left, result);
        houMap1(node.right, result);
        result.push(node.val);
      }
      return result;
    }
    

• 非递归实现。

  答案

  
    const houMap2 = node => {
      const result = [];
      const stack = [];
      let currentNode = node;
      let pre = null;
      while (currentNode || stack.length) {
        while (currentNode) {
          stack.push(currentNode);
          currentNode = currentNode.left;
        }
        currentNode = stack[stack.length - 1];
        if (!currentNode.right || currentNode.right === pre) {
          currentNode = currentNode.pop();
          pre = currentNode;
          result.push(currentNode.val);
          currentNode = null;
        } else {
          currentNode = currentNode.right;
        }
      }
    }
    

重建二叉树

已知前序遍历和中序遍历，返回二叉树

答案

  const resetTree = (pre, mid) => {
    if (pre.length === 0) return null;
    if (pre.length === 1) return new Node(pre[0]);
    const root = pre[0];
    const index = mid.indexOf(root);
    const preLeft = pre.slice(1, index + 1);
    const preRight = pre.slice(index + 1);
    const midLeft = mid.slice(0, index);
    const midRight = mid.slice(index + 1);
    root.left = resetTree(preLeft, midLeft);
    root.right = resetTree(preRight, midRight);
    return root;
  }
  

已知前序遍历和中序遍历，返回后序遍历

答案

  const returnHouMap = (pre, mid, result = []) => {
    if (pre.length === 0) return null;
    if (pre.length === 1) return pre[0];
    const root = pre[0];
    const index = mid.indexOf(root);
    const preLeft = pre.slice(1, index + 1);
    const preRight = pre.slice(index + 1);
    const midLeft = mid.slice(0, index);
    const midRight = mid.slice(index + 1);
    const leftNode = returnHouMap(preLeft, midLeft, result);
    const rightNode = returnHouMap(preRight, midRight, result);
    result.push(leftNode, rightNode, root);
    return result;
  }
  

对称二叉树

判断一颗树是否为对称的

答案

  const isDuiChen = root => {
    if (root) {
      return isSameNode(root.left, root.right);
    }
    return false;
  }
  const isSameNode = (aNode, bNode) => {
    if (!aNode && !bNode) return true;
    if (!aNode || !bNode) return false;
    if (aNode.val !== bNode.val) return false;
    return isSameNode(aNode.left, bNode.right) && isSameNode(aNode.right, bNode.left);
  }
  

二叉树的镜像

将一颗二叉树转换成其镜像返回

答案

  const returnJingXiang = root => {
    if (!root) return root;
    returnJingXiang(root.left);
    returnJingXiang(root.right);
    const leftNode = root.left;
    const rightNode = root.right;
    root.left = rightNode;
    root.right = leftNode;
    return root;
  }
  

二叉搜索树的第K个节点

给定一个二叉搜索树，找出其中的第K小的节点

答案

  const findKNode = (root, k) => {
    const stack = [];
    let currentNode = root;
    while (currentNode || stack.length) {
      while (currentNode) {
        stack.push(currentNode.left);
        currentNode = currentNode.left;
      }
      currentNode = stack.pop();
      k--;
      if (k === 0) return currentNode.val;
      currentNode = currentNode.right;
    }
    return null;
  }
  

二叉搜索树的后序遍历

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果

答案

  const isHouMap = arr => {
    if (arr && arr.length) {
      const root = arr[arr.length - 1];
      let i = 0;
      for (; i < arr.length - 1; i++) {
        if (arr[i] > root) break;
      }
      let j = i;
      for (; j < arr.length - 1; j++) {
        if (arr[j] < root) return false;
      }
      let left = true;
      if (i > 0) {
        left = isHouMap(arr.slice(0, i));
      }
      let right = true;
      if (j < arr.length - 1) {
        right = isHouMap(arr.slice(i, j));
      }
      return left && right;
    }
    return false;
  }
  

二叉树的最大深度

给定一个二叉树，找出其最大深度

答案

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

二叉树的最小深度

给定一个二叉树。找出其最下深度

答案

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

平衡二叉树

输入一颗二叉树，判断二叉树是否为平衡二叉树

答案

  const ispingHeng = root => {
    if (!root) return true;
    return [0, 1].includes(Math.abs(getMaxDepth(root.left) - getMaxDepth(root.right)));
  }
  

二叉树中和胃某一值的路径

输入一颗二叉树的根结点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。

路径定义为从树的根结点开始往下已知到叶结点所形成的一条路径。

答案

  const getPath = (root, num) => {
    const result = [];
    if (root) handlePath(root, num, result, [], 0);
    return result;
  }
  const handlePath = (node, num, result, stack, sum) => {
    stack.push(node.val);
    sum += node.val;
    if (!node.left && !node.right && sum === num) result.push([...stack]);
    if (node.left) handlePath(node.left, num, result, stack, sum);
    if (node.right) handlePath(node.right, num, result, stack, sum);
    stack.pop();
  }
  

二叉搜索树与双向链表

输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表

要求不能创建任何新的结点，只能调整树中结点指针的指向。

答案

  const changeTree = root => {
    if (root) {
      let currentNode = root;
      handleChangeTree(root, null);
      while (currentNode) {
        currentNode = currentNode.left;
      }
      return currentNode;
    }
    return null;
  }
  const handleChangeTree = (node, pre) => {
    if (node.left) {
      pre = handleChangeTree(node.left, pre);
    }
    node.left = pre;
    if (pre) {
      pre.right = node;
    }
    pre = node;
    if (node.right) {
      pre = handleChangeTree(node.right, pre);
    }
    return pre;
  }
  

序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树

答案

  const serize = node => {
    const result = [];
    if (!node) {
      result.push(null);
    } else {
      result.push(node.val);
      serize(node.left);
      serize(node.right);
    }
    return result;
  }
  const deserize = arr => {
    if (!arr.length) return null;
    const root = arr.shift();
    if (root !== null) {
      const node = new Node(root.val);
      node.left = deserize(arr);
      node.right = deserize(arr);
      return node;
    }
    return null;
  }
  

二叉树的下一个节点

给定一个二叉树中的一个节点，请找出中序遍历顺序的下一个节点并且返回。

注意树中的节点不仅仅包含左右节点，同时还包含指向父节点的指针

答案

  const getNextNode = target => {
    if (!target) return null;
    if (target.right) {
      let node = target.right;
      while (node.left) {
        node = node.left;
      }
      return node;
    } else {
      while (target) {
        if (!target.next) {
          return null;
        }
        if (target === target.pre.left) {
          return target;
        }
        target = target.next;
      }
      return target;
    }
  }
  

树的子结构

输入两颗二叉树A、B，判断B是不是A的子结构。

约定空树不是任何树的子结构。

答案

  const isChildTree = (aNode, bNode) => {
    let result = false;
    if (aNode && bNode) {
      if (aNode === bNode) {
        result = isSameTree(aNode, bNode);
      }
      if (!result) {
        result = isChildTree(aNode.left, bNode);
      }
      if (!result) {
        result = isChildTree(aNode.right, bNode);
      }
    }
    return result;
  }
  const isSameTree = (aNode, bNode) => {
    if (bNode === null) return true;
    if (aNode === null || aNode !== bNode) return false;
    return isSameTree(aNode.left, bNode.left) && isSameTree(aNode.right, bNode.right);
  }