654.最大二叉树

思路

没啥特别的思路，前序遍历加递归即可

注意

顾名思义，begin()就是指向容器第一个元素的迭代器 如果你是初学者，你可能会猜到 end()是指向容器最后一个元素的迭代器， 但事实并非如此，实际上，end()是指向容器最后一个元素的下一个位置的迭代器

如果不做判断，就会出现溢出的现象

1. 当 maxIndex 为 0 时:

   • leftNums 会试图从 nums.begin() 到 nums.begin() 创建一个向量，这将导致一个空的 leftNums 向量。

   • 当你调用 travesal(leftNums) 时，由于 leftNums 是空的，函数内部的 nums.size() == 1 条件将永远不会满足，导致无限递归，最终堆栈溢出。

2. 当 maxIndex 为 nums.size() - 1 时:

   • rightNums 会试图从 nums.end() 到 nums.end() 创建一个向量，同样会导致空的 rightNums 向量，并引发与上面相同的问题。

	if (maxIndex > 0) {
      vector<int> leftNums(nums.begin(), nums.begin() + maxIndex);
      node->left = travesal(leftNums);
    }

    if (maxIndex < nums.size() - 1) {
      vector<int> rightNums(nums.begin() + maxIndex + 1, nums.end());
      node->right = travesal(rightNums);
    }

class Solution {
public:
  TreeNode *travesal(vector<int> &nums) {
    TreeNode *node = new TreeNode();
    if (nums.size() == 1) {
      node->val = nums[0];
      return node;
    }
    int max = INT_MIN;
    int maxIndex = 0;
    for (int i = 0; i < nums.size(); i++) {
      if (nums[i] > max) {
        max = nums[i];
        maxIndex = i;
      }
    }
    node->val = max;
	//下面这两个判断必须加，不然会报错
    if (maxIndex > 0) {
      vector<int> leftNums(nums.begin(), nums.begin() + maxIndex);
      node->left = travesal(leftNums);
    }

    if (maxIndex < nums.size() - 1) {
      vector<int> rightNums(nums.begin() + maxIndex + 1, nums.end());
      node->right = travesal(rightNums);
    }

    return node;
  }
  TreeNode *constructMaximumBinaryTree(vector<int> &nums) {
    return travesal(nums);
  }
};

617.合并二叉树

思路

中序遍历加递归即可，也可以用层序遍历

题解

class Solution {
public:
  TreeNode *mergeTrees(TreeNode *root1, TreeNode *root2) {
    if (!root1) {
      return root2;
    }
    if (!root2) {
      return root1;
    }

    root1->val += root2->val;

    root1->left = mergeTrees(root1->left, root2->left);
    root1->right = mergeTrees(root1->right, root2->right);

    return root1;
  }
};

• 迭代法

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        queue<TreeNode*> que;
        que.push(t1);
        que.push(t2);
        while(!que.empty()) {
            TreeNode* node1 = que.front(); que.pop();
            TreeNode* node2 = que.front(); que.pop();
            // 此时两个节点一定不为空，val相加
            node1->val += node2->val;

            // 如果两棵树左节点都不为空，加入队列
            if (node1->left != NULL && node2->left != NULL) {
                que.push(node1->left);
                que.push(node2->left);
            }
            // 如果两棵树右节点都不为空，加入队列
            if (node1->right != NULL && node2->right != NULL) {
                que.push(node1->right);
                que.push(node2->right);
            }

            // 当t1的左节点 为空 t2左节点不为空，就赋值过去
            if (node1->left == NULL && node2->left != NULL) {
                node1->left = node2->left;
            }
            // 当t1的右节点 为空 t2右节点不为空，就赋值过去
            if (node1->right == NULL && node2->right != NULL) {
                node1->right = node2->right;
            }
        }
        return t1;
    }
};

700.二叉搜索树中的搜索

思路

二叉搜索树是一个有序树：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

• 它的左、右子树也分别为二叉搜索树

对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向

我的解法

• 递归法（体现回溯思想）

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
      if (root == NULL || root->val == val) {return root;}

      TreeNode* leftResult = searchBST(root->left, val);
        if (leftResult != nullptr) {
            return leftResult; // 在左子树中找到了目标值
        }

        TreeNode* rightResult = searchBST(root->right, val);
        return rightResult; // 在右子树中查找，或者返回空（没有找到）
    }
};

题解

递归法

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;
    }
};

或者我们也可以这么写

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == NULL || root->val == val) return root;
        if (root->val > val) return searchBST(root->left, val);
        if (root->val < val) return searchBST(root->right, val);
        return NULL;
    }
};

迭代法

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root != NULL) {
            if (root->val > val) root = root->left;
            else if (root->val < val) root = root->right;
            else return root;
        }
        return NULL;
    }
};

98.验证二叉搜索树

思路

递归

实际上没想的那么简单

• 陷阱1

不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。

• 陷阱2

样例中最小节点 可能是int的最小值，如果这样使用最小的int来比较也是不行的。此时可以初始化比较元素为longlong的最小值。

题解

递归法

• 解法一.转换成数组

class Solution {
public:
  vector<int> vec;
  void traversal(TreeNode *node) {
    if (!node) {
      return;
    }
    traversal(node->left);
    vec.push_back(node->val);
    traversal(node->right);
  }
  bool isValidBST(TreeNode *root) {
    traversal(root);
    for (int i = 1; i < vec.size(); i++) {
      // 注意要小于等于，搜索树里不能有相同元素
      if (vec[i] <= vec[i - 1])
        return false;
    }
    return true;
  }
};

• 解法二.递归遍历比较

中序遍历，一直更新maxVal，一旦发现maxVal >= root->val，就返回false，注意元素相同时候也要返回false。实际上还是利用了中序遍历的特点。

class Solution {
public:
    long long maxVal = LONG_MIN; // 因为后台测试数据中有int最小值
    bool isValidBST(TreeNode* root) {
        if (root == NULL) return true;

        bool left = isValidBST(root->left);
        // 中序遍历，验证遍历的元素是不是从小到大
        if (maxVal < root->val) maxVal = root->val;
        else return false;
        bool right = isValidBST(root->right);

        return left && right;
    }
};

反思

总是不知道递归函数最下面的return要不要填，以及要填什么。