算法题之树 | GeniusFunny的个人博客

算法题之树

GeniusFunny 12月 27, 2019

算法题之树~~~~

树的遍历

题目

完成二叉树的前序遍历、中序遍历、后序遍历、层序遍历

解决方案

前中后遍历可用递归解决

function preOrder(root) {
  if (!root) return;
  console.log(root.val)
  if (root.left) preOrder(root.left);
  if (root.right) preOrder(root.right);
}
function inOrder(root) {
  if (!root) return;
  if (root.left) inOrder(root.left);
  console.log(root.val)
  if (root.right) inOrder(root.right);
}
function postOrder(root) {
  if (!root) return;
  if (root.left) inOrder(root.left);
  if (root.right) inOrder(root.right);
  console.log(root.val)
}

后序遍历即BFS

function layerTravel(root) {
  const queue = []
  queue.push(root);
  while(queue.length) {
    let node = queue.shift();
    if (node.left) queue.push(node.left)
    if (node.right) queue.push(node.right)
    console.log(node.val)
  }
}

重建二叉树

题目

给出二叉树的先序遍历和中序遍历，还原二叉树

解决方案

先序遍历序列的首节点即为树的root节点
通过root节点可以定位到根节点在中序遍历的位置，进而划分左右子树
计算出左子树的长度
- 若左子树长度 > 0, 构建左子树
- 若先序序列长度 > 左子树长度，构建右子树

递归计算

function buildBinaryTree(preOrder, inOrder) {
  const length = preOrder.length;
  function buildBinaryTreeCore(preOrderStart, preOrderEnd, inOrderStart, inOrderEnd) {
    const rootValue = preOrder[preOrderStart];
    const root = new BinaryTree(rootValue)
    //只有一个节点
    if (preOrderStart === preOrderEnd) {
      if (inOrderStart === inOrderEnd && preOrder[preOrderStart] === inOrder[inOrderStart]) return root;
      else {
        console.log('fuck')
        return null;
      }
    }
    // 计算出root节点在中序遍历序列的位置
    let rootPositionOfInOrder = inOrderStart;
    for(let i = inOrderStart; i < inOrderEnd; i++) {
      if (rootValue === inOrder[i]) {
        rootPositionOfInOrder = i;
      }
    }
  
    let leftLength = rootPositionOfInOrder - inOrderStart; // 计算出左子树的长度
    let leftPreOrderEnd = preOrderStart + leftLength; // 在先序序列里标记最后一个左子树节点
    if (leftLength > 0) {
      root.left = buildBinaryTreeCore(preOrderStart+1, leftPreOrderEnd, inOrderStart, inOrderStart-1);
    }
    if (leftLength < preOrderEnd - preOrderStart) {
      root.right = buildBinaryTreeCore(leftPreOrderEnd+1, preOrderEnd, rootPositionOfInOrder+1, inOrderEnd)
    }
    return root;
  }
  if (preOrder === null || inOrder === null) return null;
  return buildBinaryTreeCore(0, length-1, 0, length-1);
}

二叉搜索树的后序遍历序列

二叉搜索树

若左子树非空，则左子树上的所有节点小于它的根节点值。
若右子树非空，则右子树上所有节点大于它的根节点值。
左右子树也是二叉搜索树

题目

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是，则返回true；若不是，返回false。

解决方案

后序遍历，末尾的数字为根节点，序列前半部分都小于根节点，序列后半部分大于根节点

只需要判断序列是否出现过小-大-小这样的情形

出现则为非后序遍历
未出现则继续递归判断左右子树的后序遍历序列

function postSequenceOfBST(seq) {
  function postSequenceOfBSTCore(seq, start, end) {
    if (end - start <= 2) return true;
    let bigIndex = smallerIndex = -1;
    for(let i = start; i < end; i++) {
      // 如果当前节点小于根节点
      if (seq[i] < seq[end]) {
        // 如果在之前节点出现过比根节点大的节点，则此树为非二叉搜索树
        if (bigIndex !== -1) {
          return false;
        } else {
          smallerIndex = i;
        }
      } else {
        if (bigIndex === -1) bigIndex = i;
      }
    }
    debugger
    if (smallerIndex === -1 || bigIndex === -1) {
      return postSequenceOfBSTCore(seq, start, end-1);
    } else {
      return postSequenceOfBSTCore(seq, start, bigIndex-1) && postSequenceOfBSTCore(seq, bigIndex, end-1);
    }
  }
  return postSequenceOfBSTCore(seq, 0, seq.length-1);
}

二叉树的深度

题目

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点一次经过的节点形成树的一条路径，最长路径的长度即为树的深度

解决方案

要求二叉树的深度，即求max（左子树深度，右子树深度） + 1

递归解决

function deepOfTree(root) {
  if (!root) return 0;
  return Math.max(deepOfTree(root.left)+1, deepOfTree(root.right)+1);
}

22、反转二叉树

题目

对一颗二叉树的每一个节点，交换它的左右子节点。

解决方案

递归调用交换左右节点即可，先交换子节点最后交换父节点

function reverse(root) {
  if (!root) return null;
  if (root.left) reverse(root.left);
  if (root.right) reverse(root.right);
  let temp = root.left;
  root.left = root.right
  root.right = temp;
}

二叉树的下一节点

题目

给定一棵二叉树和其中一个节点，如何找出中序遍历序列的下一个节点。树的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。

解决方案

若该节点有右子树，则下一节点时右子树中最左子节点
若该节点无右子树，并且此节点为父节点的左节点，则下一节点为父节点

若该节点无右子树且此节点为父节点的右节点，则下一节点为某主先节点的右子节点

function findNextTreeNode(root, node) {
  if (!root || !node) return null;
  if (node.right) {
    // 如果有右子树
    let leftNode = node.right;
    while(true) {
      if (leftNode.left) leftNode = leftNode.left
      else return leftNode;
    }
  }
  // 如果无右子树且是父节点的左节点
  else if(!node.right && node.parent.left === node) return node.parent;
  else {
    // 无右子节点且为父节点的右节点
    let parent = node.parent;
    while(true) {
      if (!parent.parent) return null;
      if (parent === parent.parent.left) return parent.parent
      else parent = parent.parent
    }
  }
}

树的子结构

题目

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

解决方案

首先在A中找出B的根节点所在的位置

判断B的子树是否在A中

function hasSubTree(treeA, treeB) {
  if ( !treeA || !treeB) return false;
  let result = false;
  if (treeA.val === treeB.val) {
    result = doesTreeAHasTreeB(treeA, treeB);
  }
  if (!result) result = hasSubTree(treeA.left, treeB);
  if (!result) result = hasSubTree(treeA.right, treeB);
  return result;
}

function doesTreeAHasTreeB(treeA, treeB) {
  if (!treeB) return true; // 如果treeB为空，则直接返回true
  if (!treeA) return false; // 若treeA不存在，则直接返回false

  if (treeA.val !== treeB.val) return false; // 若首节点不同，直接返回fasle
  
  return doesTreeAHasTreeB(treeA.left, treeB.left) && doesTreeAHasTreeB(treeA.right, treeB.right); // 当前节点相同，继续判断子节点
}

对称的二叉树

题目

请实现一个函数，用来判断一棵二叉树是不是对称的、如果一棵树和它的镜像相等，那么就是对此的。

解决方案

判断根节点是否为null，若是则返回true

判断左右子节点是否相等

相等则继续判断其左右子节点（递归）
- 都会空则返回true
不等则返回false

function mirrorSymmetry(root) {
  if (!root) return true;
  return mirrorSymmetryCore(root.left, root.right);
}
function mirrorSymmetryCore(left, right) {
    if (!left && !right) return true; // null === null
    if (left && right && left.val === right.val) {
      return mirrorSymmetryCore(left.left, right.right) && mirrorSymmetryCore(left.right, right.left);
    } else {
      return false;
    }
  }

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

题目

输入一棵二叉树和一个整数，打印出二叉树中节点值和为输入整数的所有路径。从根节点开始往下一直到叶节点经过的节点形成一条路径。

解决方案

先序遍历 + dfs

如果走到叶子节点此时经过的节点和不等于sum，则回溯到上一个节点；否则打印路径

// 打印所有路径
function findPathEqualSum(root, sum) {
  let current = 0;
  let path = [];

  function findPathEqualSumCore(node, sum) {
    if (node === null) return;
    path.push(node.val);
    current += node.val;
    if (current === sum && !node.left && !node.right) {
      console.log(path.join('->'));
      current = current - node.val
      path.pop();
    }
    if (node.left) findPathEqualSumCore(node.left, sum);
    if (node.right) findPathEqualSumCore(node.right, sum);
    path.pop();
    current -= node.val;
  }
  findPathEqualSumCore(root, sum)
}

// 打印一条路径
function findPathEqualSum(root, sum) {
  let current = 0;
  let path = [];

  function findPathEqualSumCore(node, sum) {
    let target = false;
    if (node === null) return false;

    path.push(node.val);
    current += node.val;
    if (current === sum && !node.left && !node.right) {
      return true;
    }
    if (node.left) target = findPathEqualSumCore(node.left, sum);
    if (target) return true;
    if (node.right) target = findPathEqualSumCore(node.right, sum);
    if (target) return true;
    path.pop();
    current -= node.val;
    return false;
  }
  findPathEqualSumCore(root, sum)
}

二叉搜索树的第k小节点

题目

给定一棵二叉搜索树，请找出其中第k大的节点。

解决方案

二叉搜索树的中序遍历即为：从小到大的序列，所以根据这个特性来解决

实现一：将遍历存储在数组中

function kthOfBST(root, k) {
  let numbers = []
  kthOfBSTCore(root, k)
  function kthOfBSTCore(root, k) {
    if (!root) return;
    if (root.left) {
      kthOfBSTCore(root.left, k--)
    }
    numbers.push(root.val)
    if (root.right) {
      kthOfBSTCore(root.right, k--)
    }
  }
  return numbers[k-1]
}

实现二：直接返回对应的数字

function kthOfBST2(root, k) {
  if (!root || !k) return null;
  function kthOfBST2Core(root) {
    let target = null;
    if (root.left) target = kthOfBST2Core(root.left, k);
    if (!target) {
      if (k === 1) target = root;
      k--
    }
    if (target == null && root.right) {
      target = kthOfBST2Core(root.right, k)
    }
    return target;
  }
  return kthOfBST2Core(root, k);
}

###