leetcode刷题/二叉树 一招鲜吃下大部分构造二叉树

一招鲜吃下大部分构造二叉树

105. 从前序与中序遍历序列构造二叉树

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

解题思路:

本体的解题思路如下:

• 前序数组的第一个元素就为根,根据这个根在中序数组分为左右数组.就是左子树和右子树.
• 前序数组先删去头节点(直接begin迭代器往下移即可),根据中序数组分之后的左右数组的个数分前序数组的左右数组.
• 然后该节点的左孩子就递归前序数组的左数组和中序数组的左数组,右孩子就递归前序数组的右数组和中序数组的右数组
• 知道数组的长度为1,说明为叶子节点.直接返回该节点.或者长度为0,说明为空节点.返回nullptr递归结束条件

到这里基本思路就明确了,每次都取第一个节点然后分数组,直到数组长度为0或者为1就返回;

代码如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {    
    //如果长度为0,说明是空节点
	if (preorder.size() == 0)
		return nullptr;
    //如果长度为1,直接返回节点.
	int val = preorder[0];
	TreeNode *cur = new TreeNode(val);
	if (preorder.size() == 1)
		return cur;

    //在中序数组中找到该值的迭代器
	vector<int>::iterator it = find(inorder.begin(), inorder.end(), val);

    //中序数组根据迭代器分为左右数组,注意区间统一,均为左闭右开.
	vector<int> inorder_left(inorder.begin(), it);
	vector<int> inorder_right(++it, inorder.end());

    //头节点抛弃
	auto pit = ++preorder.begin();
    //根据中序数组的左右数组长度分为左右数组.
	vector<int> preorder_left(pit, pit + inorder_left.size());
	vector<int> preorder_right(pit + inorder_left.size(), preorder.end());

    //递归创建左孩子和右孩子
	cur->left = buildTree(preorder_left, inorder_left);
	cur->right = buildTree(preorder_right, inorder_right);

    //返回节点
	return cur;
    }
};

❀完成这道题之后,下面有一些类似的题目:❀

106. 从中序与后序遍历序列构造二叉树

题意:

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

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

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

    3
   / \\
  9  20
    /  \\
   15   7

解题思路:

与上面步骤完全一致,就是前序遍历的根节点在第一个,后序数组的根节点在数组的最后一个.我直接给代码,代码上有详细注释.这道题我用了不同的分发,不用迭代器分.其实迭代器可能更快.

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    //如果长度为0,说明是空节点
	if (postorder.size() == 0)
		return nullptr;
    //如果长度为1,直接返回节点.
	TreeNode *root = new TreeNode(postorder.back());
	if (postorder.size() == 1)
		return root;

    //在中序遍历中寻找后序数组中最后一个数字的位置,并记录
	int index;
	for (index = 0; index < inorder.size(); index++)
	{
		if (inorder[index] == postorder.back()) 
			break;
	}
        
    //中序数组根据迭代器分为左右数组,注意区间统一,均为左闭右开.
	vector<int> inor_first(inorder.begin(), inorder.begin() + index);
	vector<int> inor_second(inorder.begin() + index + 1, inorder.end());
        
	//去除最后一个节点,在头部去除会有很高的时间复杂度,但是尾部去除就没用这个烦恼
    postorder.pop_back();
        
    //后序数组根据中序数组的左右数组长度分为左右数组.
	vector<int> postor_first(postorder.begin(), postorder.begin() + inor_first.size());
	vector<int> postor_second(postorder.begin() + inor_first.size(), postorder.end());

    //递归创建左孩子和右孩子
	root->left = buildTree(inor_first, postor_first);
	root->right = buildTree(inor_second, postor_second);

	//返回节点
	return root;
    }
};

654. 最大二叉树

题意:

给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：

二叉树的根是数组 nums 中的最大元素。
左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
返回有给定数组 nums 构建的 最大二叉树 。

示例 1：

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

示例 2：

输入：nums = [3,2,1]
输出：[3,null,2,null,1]

解题思路:

总体想法与上面一致,只是改变了寻找根(分开左右数组的节点)的方式改变.现在是每次都寻找数组中的最大值为根,然后分为左右数组.递归即可

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    //如果是空数组,说明是空节点
	if (nums.size() == 0)
		return nullptr;
    //如果数组长度为1,说明为叶子节点
    if(nums.size() == 1)
        return new TreeNode(nums[0]);

    //寻找最大值下标
	int index = 0;
	for (int i = 0; i < nums.size(); i++)
	{
		if (nums[index] < nums[i])
			index = i;
	}
    //创建新节点
	TreeNode *cur = new TreeNode(nums[index]);

    //用下标分为左右数组
	vector<int> left_n(nums.begin(), nums.begin() + index);
	vector<int> right_n(nums.begin() + index + 1, nums.end());
        
    //递归创造左孩子和右孩子
	cur->left = constructMaximumBinaryTree(left_n);
	cur->right = constructMaximumBinaryTree(right_n);
	//返回节点
	return cur;
    }
};

总结:

这种题的我基本都是用这种思路做的,可能时间复杂度有点高,但是也还能接受.