1.计算带权路径长度
2.中序遍历二叉树
3.计算二叉树最大深度
4.计算二叉树最大宽度
5.复制二叉树
6.计算结点个数
7.计算叶结点个数
8.判断二叉树是否相等
9.交换二叉树的左右结点
10.层次遍历二叉树同时输出度为1的结点数
11.输出所有从叶子结点到根结点的路径
12.判断是否为完全二叉树

1.思路：
如果结点为不纳入计算同时进行返回。
否则如果结点为叶子结点则返回结点值与路径的乘积
否则返回，左子树的路径增加+右子树的路径长度增加

int dfs(TreeNode* root, int path)//计算带权路径长度
    {
        if(!root) return 0;
        else if(!root->left && !root->right) return root->val * path;
        else return dfs(root->left, path + 1) + dfs(root->right, path + 1);//注意是path+1而不是path++注意在递归函数中不要出现++操作
    }
    int pathSum(TreeNode* root) {
        return dfs(root, 0);
    }

2.LDR

void Tra(TreeNode* root)//中序遍历二叉树
    {
        if(root)
        {
            // cout << root ->val << " ";//双序遍历二叉树
            Tra(root->left);
            cout << root->val << " ";
            Tra(root->right);
        }
    }
    int pathSum(TreeNode* root) {
        Tra(root);
    }

3.思路:返回左子树与右子树长度最长的,空结点不计算深度

int depth(TreeNode* root)//计算二叉树的深度
    {
        if(!root) return 0;
        int n = depth(root->left);
        int m = depth(root->right);
        return m > n ? m + 1: n + 1;
    }
    int pathSum(TreeNode* root) {
        cout << depth(root) << endl;
    }

4.思路：使用队列层次遍历每一层二叉树，将每一层结点纳入队列中，用队头指针和队尾指针控制在队元素，当队列中有元素时，将它的左右子树分别纳入队列，同时用一个指针指向该层结点的末尾用于控制最大结点数

const int N = 1000;
    int Width(TreeNode* T)
    {
        if(T == NULL) return 0;
        else
        {
            TreeNode* Q[N];
            int f, r ,l;//队头指针，队尾指针，以及指向某层最后结点指针初始第一层只有1
            f = r = l = 1;
            int tmp,maxw;//临时宽度，最终宽度
            tmp = maxw = 0;
            Q[r] = T;//将结点入队
            while(f <= l)//遍历每一层结点
            {
                auto p = Q[f ++];//将队头出队
                tmp ++;//临时宽度改变
                if(p->left != NULL) Q[++ r] = p->left;//如果出队结点含有左右子树则分别入队
                if(p->right != NULL) Q[++ r] = p->right;
                if(f > l)//如果队头指针超过了指向该层结点末尾的指针
                {
                    l = r;//指向下一层末尾结点
                    if(tmp > maxw) maxw = tmp;//更新最终长度
                    tmp = 0;//更新临时长度
                }
            }
            return maxw;
        }
    }

    int pathSum(TreeNode* root) {
        cout <<Width(root) << endl;
    }

int Width(TreeNode* root)
    {
        if(!root) return 0;
        else
        {
            TreeNode* q[100];
            int tt = -1, hh = 0;
            q[++ tt] = root; 
            int tmp,max;
            tmp = max = 0;
            int last = 0;
            while(hh <= last)
            {
                auto t = q[hh ++];
                tmp ++;
                if(t ->left) q[++ tt] = t->left;
                if(t ->right) q[++ tt] = t->right;
                if(hh > last)
                {
                    if(max < tmp) max = tmp;
                    last = tt;
                    tmp = 0;
                }
            }
            return max;
        }
    }

5.复制二叉树

void Copy(TreeNode* root, TreeNode* &T)//将二叉树root复制给T
    {
        if(root == NULL) T = NULL;
        else
        {
            T = new TreeNode(root->val);
            Copy(root->left, T->left);
            Copy(root->right, T->right);
        }
    }

6.计算结点个数

int LeafCount(TreeNode* root)//计算二叉树叶结点个数
    {
        if(!root) return 0;
        else if(!root->left && !root->right) return 1;
        else return LeafCount(root->left) + LeafCount(root->right);
    }

7.计算结点个数

    int NodeCount(TreeNode *root)//计算二叉树结点个数
    {
        if(!root) return 0;
        else return NodeCount(root->left) + NodeCount(root->right) + 1;
    }

8.判断二叉树是否相等

    bool isEqual(TreeNode* root, TreeNode* T)
    {
        if(root == NULL && T == NULL) return 1;
        else if(root == NULL || T == NULL) return 0;
        if(root->val != T->val) return 0;
        int l = isEqual(root->left, T->left);
        int r = isEqual(root->right, T->right);
        return l && r;
    }

9.交换二叉树啊的左右孩子

    void Swap(TreeNode*& root)//交换二叉树的左右孩子，如果其中有一个为空则不交换，如果到达的改点为空则返回
    {
        if(!root) return;
        if(!root->left && !root->right) return;
        else
        {
            TreeNode* tmp;
            tmp = root->left;
            root->left = root->right;
            root->right = tmp;
        }
        Swap(root->left);
        Swap(root->right);
    }

10.层次遍历

TreeNode* q[100];
    int tt = -1, hh = 0;
    int num = 0;
    void Level(TreeNode* T)//层次遍历二叉树同时返回度为1的结点
    {
        if(T)
        {
            q[++ tt] = T;
            while(hh <= tt)
            {
                TreeNode* p = q[hh ++];
                cout << p->val << " ";
                if( (!p->left && p->right) || (!p->right && p->left))
                    num += 1;
                if(p->left) q[++ tt] = p->left;
                if(p->right) q[++ tt] = p->right;
            }

        }
        cout << endl;
    }

    int pathSum(TreeNode* root)
    {
        Level(root);
        cout << num << endl;
    }

void Level1(TreeNode* T)
    {
        TreeNode* q[100];
        int tt = -1, hh = 0;
        int last = 0;
        q[++ tt] = T;
        while(last >= hh)
        {
            auto t = q[hh ++];
            cout << t->val << " ";
            if(t->left) q[++ tt] = t->left;
            if(t->right) q[++ tt] = t->right;
            if(last < hh) {last = tt; cout << endl; }
        }
    }

11.输出所有从叶子结点到根结点路径

void dfs(TreeNode* T, int path[], int l)//输出所有从叶子结点到根结点的路径，先序遍历
    {
        if(T)
        {
            if(!T->left && !T->right)
            {
                cout <<" "<< T->val << "到根结点路径："<< T->val << " ";
                for(int i = l - 1;i >= 0 ;i --)
                    cout << path[i]<< " ";
                cout <<  endl;

            }
            else
            {
                path[l] = T->val;
                l ++;
                dfs(T->left, path, l);
                dfs(T->right, path, l);
                l --;
            }
        }
    }

    int pathSum(TreeNode* root)
    {
        int a[100];
        dfs(root, a, 0);
        cout << endl;
    }

12.判断是否为完全二叉树
思想：出队结点为空时后续结点必须为空否则为假，出队结点不为空时则将左右孩子入队

    bool IsComple(TreeNode* T)
    {
        if(!T) return true;
        else
        {
            TreeNode* q[100];
            int tt = -1, hh = 0;
            q[++ tt] = T;
            while(tt >= hh)
            {
                auto t = q[hh ++];
                if(t)
                {
                    q[++ tt] = t->left;
                    q[++ tt] = t->right;
                }
                else
                    while(tt >= hh)
                    {
                        auto p = q[hh ++];
                        if(p) return false;
                    }
            }
            return true;
        }
    }