重建二叉树|算法专题

# 题目1-二叉树重建

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

# 思路

前序遍历：根节点 + 左子树前序遍历 + 右子树前序遍历
中序遍历：左子树中序遍历 + 根节点 + 右字数中序遍历
后序遍历：左子树后序遍历 + 右子树后序遍历 + 根节点

根据上面的规律：

前序遍历找到根结点root
找到root在中序遍历的位置 -> 左子树的长度和右子树的长度
截取左子树的中序遍历、右子树的中序遍历
截取左子树的前序遍历、右子树的前序遍历
递归重建二叉树

# 代码

    function reConstructBinaryTree(pre, vin) {
        if(pre.length === 0){
            return null;
        }
        if(pre.length === 1){
            return new TreeNode(pre[0]);
        }
        const value = pre[0];
        const index = vin.indexOf(value);
        const vinLeft = vin.slice(0,index);
        const vinRight = vin.slice(index+1);
        const preLeft = pre.slice(1,index+1);
        const preRight = pre.slice(index+1);
        const node = new TreeNode(value);
        node.left = reConstructBinaryTree(preLeft, vinLeft);
        node.right = reConstructBinaryTree(preRight, vinRight);
        return node;
    }

@前端进阶之旅: 代码已经复制到剪贴板

# 题目2-求二叉树的遍历

给定一棵二叉树的前序遍历和中序遍历，求其后序遍历

输入描述:

两个字符串，其长度n均小于等于26。第一行为前序遍历，第二行为中序遍历。二叉树中的结点名称以大写字母表示：A，B，C…最多26个结点。

输出描述:

输入样例可能有多组，对于每组测试样例，输出一行，为后序遍历的字符串。

样例：

输入
ABC
BAC
FDXEAG
XDEFAG

输出
BCA
XEDGAF

@前端进阶之旅: 代码已经复制到剪贴板

# 思路

和上面题目的思路基本相同

前序遍历找到根结点root
找到root在中序遍历的位置 -> 左子树的长度和右子树的长度
截取左子树的中序遍历、右子树的中序遍历
截取左子树的前序遍历、右子树的前序遍历
递归拼接二叉树的后序遍历

# 代码

let pre;
let vin;

while((pre = readline())!=null){
    vin = readline();
    print(getHRD(pre,vin));
}

    function getHRD(pre, vin) {
      if (!pre) {
        return '';
      }
      if (pre.length === 1) {
        return pre;
      }
      const head = pre[0];
      const splitIndex = vin.indexOf(head);
      const vinLeft = vin.substring(0, splitIndex);
      const vinRight = vin.substring(splitIndex + 1);
      const preLeft = pre.substring(1, splitIndex + 1);
      const preRight = pre.substring(splitIndex + 1);
      return getHRD(preLeft, vinLeft) + getHRD(preRight, vinRight) + head;
    }

@前端进阶之旅: 代码已经复制到剪贴板

# 考察点

二叉树
复杂问题拆解

# 题目1-二叉树重建

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

# 思路

前序遍历：根节点 + 左子树前序遍历 + 右子树前序遍历
中序遍历：左子树中序遍历 + 根节点 + 右字数中序遍历
后序遍历：左子树后序遍历 + 右子树后序遍历 + 根节点

根据上面的规律：

前序遍历找到根结点root
找到root在中序遍历的位置 -> 左子树的长度和右子树的长度
截取左子树的中序遍历、右子树的中序遍历
截取左子树的前序遍历、右子树的前序遍历
递归重建二叉树

# 代码

    function reConstructBinaryTree(pre, vin) {
        if(pre.length === 0){
            return null;
        }
        if(pre.length === 1){
            return new TreeNode(pre[0]);
        }
        const value = pre[0];
        const index = vin.indexOf(value);
        const vinLeft = vin.slice(0,index);
        const vinRight = vin.slice(index+1);
        const preLeft = pre.slice(1,index+1);
        const preRight = pre.slice(index+1);
        const node = new TreeNode(value);
        node.left = reConstructBinaryTree(preLeft, vinLeft);
        node.right = reConstructBinaryTree(preRight, vinRight);
        return node;
    }

@前端进阶之旅: 代码已经复制到剪贴板

# 题目2-求二叉树的遍历

给定一棵二叉树的前序遍历和中序遍历，求其后序遍历

输入描述:

两个字符串，其长度n均小于等于26。第一行为前序遍历，第二行为中序遍历。二叉树中的结点名称以大写字母表示：A，B，C…最多26个结点。

输出描述:

输入样例可能有多组，对于每组测试样例，输出一行，为后序遍历的字符串。

样例：

输入
ABC
BAC
FDXEAG
XDEFAG

输出
BCA
XEDGAF

@前端进阶之旅: 代码已经复制到剪贴板

# 思路

和上面题目的思路基本相同

前序遍历找到根结点root
找到root在中序遍历的位置 -> 左子树的长度和右子树的长度
截取左子树的中序遍历、右子树的中序遍历
截取左子树的前序遍历、右子树的前序遍历
递归拼接二叉树的后序遍历

# 代码

let pre;
let vin;

while((pre = readline())!=null){
    vin = readline();
    print(getHRD(pre,vin));
}

    function getHRD(pre, vin) {
      if (!pre) {
        return '';
      }
      if (pre.length === 1) {
        return pre;
      }
      const head = pre[0];
      const splitIndex = vin.indexOf(head);
      const vinLeft = vin.substring(0, splitIndex);
      const vinRight = vin.substring(splitIndex + 1);
      const preLeft = pre.substring(1, splitIndex + 1);
      const preRight = pre.substring(splitIndex + 1);
      return getHRD(preLeft, vinLeft) + getHRD(preRight, vinRight) + head;
    }

@前端进阶之旅: 代码已经复制到剪贴板

# 考察点

二叉树
复杂问题拆解