给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

 

示例 1:
image.png

输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:
image.png

示例 2:
image.png

输入:nums = [1,3]
输出:[3,1]
解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
 

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

递归就完事了

/**
 * 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* solve(vector<int>& nums, int left, int right) {
        if(left > right){
            return nullptr;
        }
        
        int mid = (left + right) / 2;
        TreeNode* node = new TreeNode(nums[mid]);
        node->left = solve(nums, left, mid - 1);
        node->right = solve(nums, mid + 1, right);
        return node;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return solve(nums, 0, nums.size() - 1);
    }
};

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

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

返回合并后的二叉树。

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

 

示例 1:
image.png

输入:root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出:[3,4,5,5,4,null,7]
示例 2:

输入:root1 = [1], root2 = [1,2]
输出:[2,2]
 

提示:

两棵树中的节点数目在范围 [0, 2000] 内
-104 <= Node.val <= 104

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/merge-two-binary-trees
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

先序遍历

if(root1 == nullptr || root2 == nullptr){
return root1 ? root1 : root2;
}
需要注意,咋们有三种情况对应三种策略
情况1:root1 == nullptr 且 root2 == nullptr 那么此时直接返回nullptr
情况2:root1 == nullptr 或 root2 == nullptr 且不均为nullptr,才是返回不为nullptr的那个结点(相当于是走不为nullptr的那个结点了)
情况3:root1 != nullptr 且 root2 != nullptr 此时结点相加 然后 root->left = mergeTrees(root1->left, root2->left); root->right = mergeTrees(root1->right, root2->right);

/**
 * 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 == nullptr || root2 == nullptr){
            return root1 ? root1 : root2;
        }
        
        TreeNode* root = new TreeNode(root1->val + root2->val);
        root->left = mergeTrees(root1->left, root2->left);
        root->right = mergeTrees(root1->right, root2->right);
        return root;
    }
};

给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。

 

示例 1:
image.png

输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]
示例 2:
image.png

输入:root = [2,1,3]
输出:[2,3,1]
示例 3:

输入:root = []
输出:[]
 

提示:

树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/invert-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

后序遍历

遍历完之后左右孩子进行交换

/**
 * 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* invertTree(TreeNode* root) {
        if(root == nullptr){
            return root;
        }
        invertTree(root->left);
        invertTree(root->right);
        TreeNode* tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        return root;
    }
};

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

 

示例 1:
image.png

输入:root = [3,9,20,null,null,15,7]
输出:true
示例 2:
image.png

输入:root = [1,2,2,3,3,null,null,4,4]
输出:false
示例 3:

输入:root = []
输出:true
 

提示:

树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/balanced-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

后序遍历

后序就完事了 int 返回高度。

/**
 * 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:
    int solve(TreeNode* node){
        if(node == nullptr){
            return 0;
        }

        int left = solve(node->left);
        int right = solve(node->right);
        if(left == -1 || right == -1){
            return -1;
        } else if(abs(left - right) > 1){
            return -1;
        } else {
            return max(left, right) + 1;
        }
    }

    bool isBalanced(TreeNode* root) {
        return solve(root) != -1;
    }
};