#include "common.h"


struct ListNode{
    ListNode* next;
    int val;
    ListNode(int v):val(v), next(nullptr){;}

};  // ListNode

struct TreeNode{
    TreeNode* left;
    TreeNode* right;
    int val;
    TreeNode(int a):val(a), left(nullptr), right(nullptr){;}

};  // TreeNode

// 合并两个链表
ListNode* Test1(ListNode* L1, ListNode* L2){
    ListNode* new_head = new ListNode(0);
    ListNode* cur = new_head;
    
    ListNode* p1 = L1;
    ListNode* p2 = L2;
    while(p1&&p1){
        if(p1->val < p2->val){
            cur->next = new ListNode(p1->val);
            cur = cur->next;
            p1 = p1->next;
        }
        else{
            cur->next = new ListNode(p2->val);
            cur  = cur->next;
            p2 = p2->next;
        }

    }

    while(p1){
        cur->next = new ListNode(p1->val);
        p1 = p1->next;
        cur = cur->next;
    }

    while(p2){
        cur->next = new ListNode(p2->val);
        p2 = p2->next;
        cur = cur->next;
    }

    cur->next = nullptr;

    return new_head->next;


}

// 输入一棵二叉树，求该树的深度。
int compute_depth(TreeNode* root){
    if(root==nullptr){
        return 0;
    }

    int left_depth = compute_depth(root->left);
    int right_depth = compute_depth(root->right);
    return max(left_depth, right_depth)+1;
}

// 非递归
int compute_depth2(TreeNode* root){
    if(root==nullptr){
        return 0;
    }
    queue<TreeNode*> q;
    q.push(root);
    int count = 0;
    while(!q.empty()){
        count++;

        int len = q.size();
        while (len-->0)
        {
            /* code */
            auto cur = q.front();
            q.pop();
            if(cur->left){
                q.push(cur->left);
            }
            if(cur->right){
                q.push(cur->right);
            }
            
        }

        
    }
    return count;
}


int main(int argc, char** argv){


    return 0;
}