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

即翻转左右子树

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

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

注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果

代码

递归法（前序遍历）
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL)return root;

        swap(root->left,root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }

};

迭代法（前序遍历）

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();              // 中
            st.pop();
            swap(node->left, node->right);
            if(node->right) st.push(node->right);   // 右
            if(node->left) st.push(node->left);     // 左
        }
        return root;
    }
};

2.对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。

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

代码

判断两个树是否完全一样
bool same(TreeNode*p,TreeNode*q)
{
    if(p==NULL&&q!=NULL)return false;
    else if(p!=NULL&&q==NULL)return false;
    else if(q==NULL&&p==NULL)return true;
    else if(q->val!=p->val)return false;

    bool left=same(p->left,q->left);
    bool right=same(p->right,q->right);
    return left&&right;

}




(递归法)
class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right) {
        // 首先排除空节点的情况
        if (left == NULL && right != NULL) return false;
        else if (left != NULL && right == NULL) return false;
        else if (left == NULL && right == NULL) return true;
        // 排除了空节点，再排除数值不相同的情况
        else if (left->val != right->val) return false;

        // 此时就是：左右节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
        bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
        bool inside = compare(left->right, right->left);    // 左子树：右、 右子树：左
        bool isSame = outside && inside;                    // 左子树：中、 右子树：中 （逻辑处理）
        return isSame;

    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};

(迭代法)
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        queue<TreeNode*> que;
        que.push(root->left);   // 将左子树头结点加入队列
        que.push(root->right);  // 将右子树头结点加入队列

        while (!que.empty()) {  // 接下来就要判断这两个树是否相互翻转
            TreeNode* leftNode = que.front(); que.pop();
            TreeNode* rightNode = que.front(); que.pop();
            if (!leftNode && !rightNode) {  // 左节点为空、右节点为空，此时说明是对称的
                continue;
            }

            // 左右一个节点不为空，或者都不为空但数值不相同，返回false
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                return false;
            }
            que.push(leftNode->left);   // 加入左节点左孩子
            que.push(rightNode->right); // 加入右节点右孩子
            que.push(leftNode->right);  // 加入左节点右孩子
            que.push(rightNode->left);  // 加入右节点左孩子
        }
        return true;
    }
};

3.设计一个算法求给定二叉树的所有双分支节点个数
代码

int result;
void dfs(TreeNode*cur)
{
    if(cur==NULL)return;
    dfs(cur->left);
    dfs(cur->right);
    if(cur->left!=NULL&&cur->right!=NULL)
    {
        result++;
    }
}

3.合并二叉树
给你两棵二叉树： root1 和 root2 。

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

返回合并后的二叉树。

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

代码

(递归法)
class Solution {
public:

    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1==NULL)return root2;
        if(root2==NULL)return root1;

        TreeNode*node = new TreeNode(0);
        node->val+=root1->val;
        node->val+=root2->val;

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

        return node;
    }
};