二叉树题解

[P1827 USACO3.4] 美国血统 American Heritage

// 其实就是前中序转后序 递归 当前序为空的时候退出，否则取前序的第一个为根，再中序中找左边为左子树，右边为右子树。注意前序中，左边的前k个就是左子树的，后面就是右子树的。
#include <bits/stdc++.h>
using namespace std;

void change(string pre, string inor)
{
	if (pre.empty())return;

	char root = pre[0];
	pre.erase(pre.begin());

	int k = inor.find(root);
	string leftinor = inor.substr(0, k);
	string rightinor = inor.substr(k + 1);
	// 注意这里
	string leftpre = pre.substr(0, k);
	string rightpre = pre.substr(k);

	change(leftpre, leftinor);
	change(rightpre, rightinor);

	cout << root;
}


int main()
{
	string pre, inor;
	cin >> inor >> pre;
	change(pre, inor);
}

449. 序列化和反序列化二叉搜索树 - 力扣（LeetCode）

class Codec:
    # 序列化比较简单 就是一个后序遍历 注意最后的return部分 ' '.join(map(str, arr)) 首先是''要有空格 然后是map的用法 把arr转str
    def serialize(self, root: Optional[TreeNode]) -> str:
        """Encodes a tree to a single string.
        """
        arr = []
        def postOrder(root):
            if root is None:
                return
            postOrder(root.left)
            postOrder(root.right)
            arr.append(root.val)
        postOrder(root)
        return ' '.join(map(str,arr))
        
	# 对于二叉搜索树来说 每个点的位置确定 所以比反序列化普通二叉树简单
    # 首先把data还原成arr 当到达叶子节点的时候（也就是当前点不能插入这个地方）返回None    从arr中取出一个数作为跟 然后取出一个数作为右孩子 取出一个数作为左孩子 （后序遍历 先右再左）然后返回根   注意 初始的时候不限范围  
    def deserialize(self, data: str) -> Optional[TreeNode]:
        """Decodes your encoded data to tree.
        """
        arr = list(map(int, data.split()))
        def construct(lower,upper):
            if arr == [] or arr[-1] < lower or arr[-1] > upper:
                return None
            val = arr.pop()
            root = TreeNode(val)
            root.right = construct(val, upper)
            root.left = construct(lower,val)
            return root
        return construct(-inf,inf)

297. 二叉树的序列化与反序列化 - 力扣（LeetCode）

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        # 前序遍历
        if root is None:
            return 'None'
        return str(root.val) + ',' + str(self.serialize(root.left)) + ',' + str(self.serialize(root.right)) 


    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        def dfs(dataList):
            val = dataList.pop(0)
            if val == 'None':
                return None
            root = TreeNode(int(val))
            root.left = dfs(dataList)
            root.right = dfs(dataList)
            return root
        dataList = data.split(',')
        return dfs(dataList)
        

1080. 根到叶路径上的不足节点 - 力扣（LeetCode）

很经典的二叉树 搜索问题 分为三步 1 判断根节点 2判断叶子节点 3递归左右 同时变化条件（limit）

这个题关键就是 看出来 只有左右都不满足的时候 （把左右都删掉）根才能不满足 如果左右没删除 说明有满足大于limit的 那么根必定是有大于limit的

/**
 * 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* sufficientSubset(TreeNode* root, int limit) 
    {
        if (root == nullptr)
            return nullptr;
        if (root->left == nullptr && root->right == nullptr)
        {
            if (limit > 0)
                root = nullptr;
            return root;
        }
        
        if (root->left) root->left = sufficientSubset(root->left, limit - root->val);
        if (root->right) root->right = sufficientSubset(root->right, limit - root->val);
        
        if (root->left == nullptr && root->right == nullptr)return nullptr;
        else return root;
    }
};