[剑指offer]38重建二叉树

2021年11月25日 阅读数:3
这篇文章主要向大家介绍[剑指offer]38重建二叉树,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

今天开始讲和你们坚持打卡面试很是重要算法练习---剑指offer,但愿咱们能一块儿肝。java

1 题目描述

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。node

2 思路----c++

  • 求出根节点(前序序列第一个元素)python

  • 将根节点带入到中序序列中求出左右子树的中序遍历序列c++

  • 经过左右子树的中序序列元素集合带入前序遍历序列求出左右子树的前序序列面试

  • 左右子树的前序序列第一个元素分别是根节点的左右儿子算法

c++版本ide

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
        //断定递归终止条件;
        if(pre.size() == 0 || in.size() == 0) {
            return NULL;
        }
        //定义Node节点并其求根节点;
        int root = pre[0];
        TreeNode* node = new TreeNode(root);
        vector<int>::iterator it;
        //1.求左右子树的遍历序列;
        vector<int> preLeft, preRight, inLeft, inRight;
        //(1).求根节点在中序遍历序列中的位置;
        vector<int>::iterator i;
        for(it = in.begin(); it != in.end(); it++) {
            if(root == *it) {
                i = it;
            }
        }
        //(2).求左右子树的中序遍历子序列;
        int k = 0;
        for(it = in.begin(); it != in.end(); it++) {
            if(k == 0) {
                inLeft.push_back(*it);
            }
            else if(k == 1) {
                inRight.push_back(*it);
            }
            else {}
            if(it == i) {
                k = 1;
            }  
        }
        //(3).求左右子树的前序遍历子序列;
        k = 0;
        vector<int>::iterator ite;
        for(it = pre.begin()+1; it != pre.end(); it++) {
            for(ite = inLeft.begin(); ite != inLeft.end(); ite++) {
                if(*it == *ite) {
                    preLeft.push_back(*it);
                    k = 1;
                }
            }
            if(k == 0) {
                preRight.push_back(*it);
            }
            k = 0;
        }
         //根据遍历序列求出跟的左右节点;
        node->left = reConstructBinaryTree(preLeft,inLeft);
        node->right = reConstructBinaryTree(preRight,inRight);
        //返回节点地址;
        return node; 
    }
};

java版本spa

import java.util.Arrays;

/*
 * 输入前序遍历和中序遍历,重建二叉树
 */

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length == 0||in.length == 0){
            return null;
        }
        TreeNode root=new TreeNode(pre[0]);
        for(int i=0;i<in.length;i++){
            if(in[i]==pre[0]){
                root.left=reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1),
                        Arrays.copyOfRange(in, 0, i));
                root.right=reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length),
                        Arrays.copyOfRange(in, i+1, in.length));
            }
        }
        return root;
    }
}

python版本code

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if pre is None or tin is None or len(pre)==0 or len(tin)==0:
            return None
        root = TreeNode(pre[0])
        i = tin.index(pre[0])
        root.left = self.reConstructBinaryTree(pre[1:1+i], tin[0:i])
        root.right = self.reConstructBinaryTree(pre[i+1:], tin[i+1:])
        return root

4 唠嗑

2020年8月10日,打卡格式"打卡XX天"。暖蓝汇聚你们一块儿,探讨简历修改,面试经历分享,尽全力让你们能在2020找到理想的工做。若是你想加入,加我拉你进面试交流群。orm