代码随想录算法训练营第十六天|654.最大二叉树，167.合并二叉树，700.二叉搜索树中的搜索

分类:热门推荐日期:2024-03-24浏览:1评论:0

 654.最大二叉树

167.合并二叉树

700.二叉搜索树中的搜索

 654.最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点，其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

 

 C++

/**
 * 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& nums) {
        TreeNode* node = new TreeNode(0);
        if (nums.size() == 1) {
            node->val = nums[0];
            return node;
        }
        // 找到数组中最大的值和对应的下标
        int maxValue = 0;
        int maxValueIndex = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
                maxValueIndex = i;
            }
        }
        node->val = maxValue;
        // 最大值所在的下标左区间 构造左子树
        if (maxValueIndex > 0) {
            vector newVec(nums.begin(), nums.begin() + maxValueIndex);
            node->left = constructMaximumBinaryTree(newVec);
        }
        // 最大值所在的下标右区间 构造右子树
        if (maxValueIndex < (nums.size() - 1)) {
            vector newVec(nums.begin() + maxValueIndex + 1, nums.end());
            node->right = constructMaximumBinaryTree(newVec);
        }
        return node;
    }
};

优化

        使用了辅助函数constructMaximumBinaryTree来接收数组的起始和终止索引，从而避免创建新的子数组：

  • 辅助函数使用索引：通过为constructMaximumBinaryTree函数添加两个额外的参数start和end，我们可以直接在原数组上操作，而不需要每次都创建新的数组或子数组。这样，我们只需在原始数组上改变索引的范围来表示不同的子数组。
  • 避免额外的数组拷贝：原始代码中通过创建新的vector实例来构造左右子树，这不仅增加了内存使用，还增加了运行时间。优化后的代码直接在原数组上通过索引操作，避免了这种额外开销。
  • 递归逻辑保持不变：优化后的代码仍然遵循找到最大值并以此构造根节点，然后递归地构造左右子树的逻辑。

    性能分析

    • 时间复杂度：O(n^2)，在最坏的情况下（数组每次都是升序或降序），每次找最大值需要O(n)，总共需要递归n次。
    • 空间复杂度：O(n)，主要是由于递归调用栈的深度。尽管避免了额外的数组拷贝，但是在构造树时仍然需要为每个节点分配空间。对于平衡的二叉树，递归调用栈的深度是O(log n)，但是在最坏的情况下（形成链表），深度是O(n)。 
      #include using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
    // 辅助函数，使用数组索引避免额外的数组拷贝
    TreeNode* constructMaximumBinaryTree(vector& nums, int start, int end) {
        if (start > end) return nullptr; // 递归的终止条件
        // 找到数组中最大值的索引
        int maxValueIndex = start;
        for (int i = start + 1; i <= end; i++) {
            if (nums[i] > nums[maxValueIndex]) {
                maxValueIndex = i;
            }
        }
        TreeNode* node = new TreeNode(nums[maxValueIndex]);
        // 递归构造左右子树
        node->left = constructMaximumBinaryTree(nums, start, maxValueIndex - 1);
        node->right = constructMaximumBinaryTree(nums, maxValueIndex + 1, end);
        return node;
    }
    TreeNode* constructMaximumBinaryTree(vector& nums) {
        return constructMaximumBinaryTree(nums, 0, nums.size() - 1);
    }
};

      python 

      class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def constructMaximumBinaryTree(self, nums) -> TreeNode:
        return self.build(nums, 0, len(nums))
    def build(self, nums, start, end):
        if start == end:
            return None
        # 找到最大值及其索引
        max_val = max(nums[start:end])
        max_index = nums.index(max_val, start, end)
        # 创建当前节点
        node = TreeNode(max_val)
        node.left = self.build(nums, start, max_index)
        node.right = self.build(nums, max_index + 1, end)
        return node

      167.合并二叉树

      给你两棵二叉树： root1 和 root2 。

      想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

      返回合并后的二叉树。

      注意: 合并过程必须从两个树的根节点开始。

      C++ 

      这种合并树的方法直接在root1上进行修改，因此不需要额外的空间来创建合并后的树（除了递归调用栈占用的空间）。这种就地修改的方法效率较高，但它改变了root1的结构和数值，所以如果原始的root1树还需要保持不变，那么这种方法就不适用。

      性能分析

      • 时间复杂度：O(n)，其中n是两棵树中节点数较小的那棵树的节点数。每个节点最多被访问一次。
      • 空间复杂度：O(h)，其中h是两棵树中较深的那棵树的高度，空间复杂度主要由递归调用栈的深度决定。在最坏的情况下，树完全不平衡，空间复杂度为O(n)；在最好的情况下，树完全平衡，空间复杂度为O(log n)。

        C++ 

        /**
 * 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* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (root1 == NULL) return root2; // 如果t1为空，合并之后就应该是t2
        if (root2 == NULL) return root1; // 如果t2为空，合并之后就应该是t1
        // 修改了t1的数值和结构
        root1->val += root2->val;                             // 中
        root1->left = mergeTrees(root1->left, root2->left);      // 左
        root1->right = mergeTrees(root1->right, root2->right);   // 右
        return root1;
    }
};

         方法二：

        • 基本情况：如果root1和root2都是nullptr，则返回nullptr作为合并后的节点，表示在这个位置上没有节点。
        • 节点值计算：如果root1或root2中的一个为空，那么合并后节点的值就是另一个非空节点的值；如果都非空，合并后节点的值是两个节点值的和。创建一个新的TreeNode作为合并后的节点。
        • 递归合并子树：递归地合并root1和root2的左子树，然后合并它们的右子树。如果root1或root2中的一个为nullptr，递归时传递nullptr表示该方向上没有子树。
        • 返回新树的根节点：最终返回新创建的节点newNode，它代表了合并后的二叉树的根节点。

          性能分析

          • 时间复杂度：O(n)，其中n是两棵树中节点数较少的那棵树的节点数。每个节点最多被访问一次，以计算新节点的值和递归合并其子树。
          • 空间复杂度：O(n)，新树的创建导致了额外的空间开销，其中n是两棵树中节点数较多的那棵树的节点数。此外，递归调用栈的深度也会占用空间，对于平衡二叉树，空间复杂度是O(log n)；对于完全不平衡的二叉树，空间复杂度是O(n)。

            这种实现方法保留了原始数据的不变性，适用于不希望修改原始输入树的场景。

            C++ 

            #include struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        // 如果两个节点都为空，则合并后的节点也为空
        if (!root1 && !root2) {
            return nullptr;
        }
        
        // 计算合并后节点的值
        int val = (root1 ? root1->val : 0) + (root2 ? root2->val : 0);
        TreeNode* newNode = new TreeNode(val);
        
        // 递归地合并左子树和右子树
        newNode->left = mergeTrees(root1 ? root1->left : nullptr, root2 ? root2->left : nullptr);
        newNode->right = mergeTrees(root1 ? root1->right : nullptr, root2 ? root2->right : nullptr);
        
        return newNode;
    }
};

            python 

            class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        # 如果两个节点都为空，则合并后的节点也为空
        if not root1 and not root2:
            return None
        
        # 如果其中一个节点为空，合并后的节点就是另一个非空节点
        # 注意这里使用了三元表达式，若root1为空，则使用root2的值，反之亦然
        val = (root1.val if root1 else 0) + (root2.val if root2 else 0)
        newNode = TreeNode(val)
        
        # 递归地合并左子树和右子树
        newNode.left = self.mergeTrees(root1.left if root1 else None, root2.left if root2 else None)
        newNode.right = self.mergeTrees(root1.right if root1 else None, root2.right if root2 else None)
        
        return newNode

            700.二叉搜索树中的搜索

            给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

            你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

            示例 1:

            输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

            示例 2:

            输入：root = [4,2,7,1,3], val = 5
输出：[]

            递归法：

            C++ 

            /**
 * 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* searchBST(TreeNode* root, int val) {
        if (root == NULL || root->val == val) return root;
        TreeNode* result = NULL;
        if (root->val > val) result = searchBST(root->left, val);
        if (root->val < val) result = searchBST(root->right, val);
        return result;
    }
};

            python 

            class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root or root.val == val:
            return root
        # 如果当前节点的值大于要查找的值，递归搜索左子树
        if root.val > val:
            return self.searchBST(root.left, val)
        # 如果当前节点的值小于要查找的值，递归搜索右子树
        if root.val < val:
            return self.searchBST(root.right, val)

            迭代法：

            迭代法相比递归法在空间复杂度上有优势，特别是在处理深度很大的二叉搜索树时，可以避免递归调用栈溢出的风险。

            C++

            struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root != nullptr && root->val != val) {
            // 根据二叉搜索树的性质选择向左或向右搜索
            root = (root->val > val) ? root->left : root->right;
        }
        return root; // 返回找到的节点，如果没有找到则为nullptr
    }
};

            python

            class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        while root and root.val != val:
            # 根据二叉搜索树的性质选择向左或向右搜索
            root = root.left if root.val > val else root.right
        return root  # 返回找到的节点，如果没有找到则为None

相关推荐

关于我们常见问题广告服务免责声明联系我们
Powered By Z-BlogPHP 1.7.3 Theme By 优美主题
Copyright Your WebSite.Some Rights Reserved. 浙ICP备2023018783号