【leetcode刷题】T118-合并两个有序链表

木又AI帮

发布于 2019-07-22 15:51:47

3740

发布于 2019-07-22 15:51:47

文章被收录于专栏：木又AI帮

木又的第118篇leetcode解题报告

二叉树类型第8篇解题报告

leetcode第105题：从前序与中序遍历序列构造二叉树

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

【题目】

根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
    3
   / \
  9  20
    /  \
   15   7

【思路】

前序遍历的顺序是根左右；中序遍历的顺序是左根右。（前序、中序、后序遍历的顺序是访问根节点的顺序）

那么前序遍历的一个元素e，在中序遍历中找到其位置，那么该位置前的元素位于左子树上，该位置后的元素位于右子树上，以此递归。

举例来说，假设前序遍历为[1,2,3]，后序遍历为[2,3,1]。

对于前序遍历第1个节点1，在中序遍历中找到其位置（第3个节点），那么[2,3]（中序遍历为[2,3]）位于根节点1的左子树上；

接着递归遍历前序遍历[2,3]中第一个节点2，在中序遍历中找到其位置（第1个节点），那么[3]位于该节点的右子树上；

接着递归遍历前序遍历[3]中第一个节点……

（python和c++的实现方式稍有不同，python直接生成子树的遍历顺序，c++通过下标来得到子树的遍历顺序）

【代码】

python版本

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        # 根左右 PK 左根右
        if len(preorder) == 0:
            return None
        root = TreeNode(preorder[0])
        num = inorder.index(preorder[0])
        left_preorder = preorder[1:num+1]
        right_preorder = preorder[num+1:]
        left_inorder = inorder[:num]
        right_inorder = inorder[num+1:]
        self.build(root, left_preorder, left_inorder, right_preorder, right_inorder)
        return root

    def build(self, node, left_preorder, left_inorder, right_preorder, right_inorder):
        if len(left_preorder) != 0:
            node.left = TreeNode(left_preorder[0])
            num = left_inorder.index(left_preorder[0])
            self.build(node.left, left_preorder[1:num+1], left_inorder[:num], left_preorder[num+1:], left_inorder[num+1:])
        if len(right_preorder) != 0:
            node.right = TreeNode(right_preorder[0])
            num = right_inorder.index(right_preorder[0])
            self.build(node.right, right_preorder[1:num+1], right_inorder[:num], right_preorder[num+1:], right_inorder[num+1:])

C++版本

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        TreeNode* root = new TreeNode(0);
        build(root, true, preorder, 0, inorder, 0, preorder.size()-1, preorder.size()-1);
        return root->left;
    }

    void build(TreeNode* node, bool left, vector<int>& preorder, int start1, vector<int>& inorder, int start2, int end1, int end2){
        int place = 0;
        if(start1 <= end1 && start2 <= end2){
            if(left){
                node->left = new TreeNode(preorder[start1]);
                node = node->left;
            }else{
                node->right = new TreeNode(preorder[start1]);
                node = node->right;
            }
            for(place = start2; place <= end2; place++){
                if(inorder[place] == preorder[start1])
                    break;
            }
            build(node, true, preorder, start1+1, inorder, start2, end1, place-1);
            build(node, false, preorder, start1+(place-start2)+1, inorder, place+1, end1, end2);
        }
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-07-16，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树