程序员面试金典

程序员面试金典 -- 输出单层结点

 

题目描述

对于一棵二叉树，请设计一个算法，创建含有某一深度上所有结点的链表。

给定二叉树的根结点指针TreeNode* root，以及链表上结点的深度，请返回一个链表ListNode，代表该深度上所有结点的值，请按树上从左往右的顺序链接，保证深度不超过树的高度，树上结点的值为非负整数且不超过100000。

 

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class TreeLevel {
public:
    void Get(TreeNode *root, int dep, ListNode* &t){
        if(dep == 1){
            ListNode *tmp = new ListNode(root->val); 
            t->next = tmp; 
            t = tmp; 
        }else{
            if(root->left){
                Get(root->left, dep-1, t); 
            }
            if(root->right){
                Get(root->right, dep-1, t); 
            }
        }
    }

    ListNode* getTreeLevel(TreeNode* root, int dep) { 
        if(dep <= 0 || root == NULL ){
            return NULL; 
        }

        ListNode *ans = new ListNode(-1); 
        ListNode *t = ans; 
        Get(root, dep, t); 
        return ans->next; 

        // write code here  

        /* 
        if(root == NULL){
            return NULL; 
        }
        int tmp_int; 
        ListNode *ans; 
        ListNode *tt = ans; 

        queue<TreeNode *> q;
        queue<int> qint; 

        q.push(root); qint.push(1); 

        while(!q.empty()){
            TreeNode *tmp = q.front(); q.pop(); 
            int tmp_int = qint.front(); qint.pop(); 

            if(dep == tmp_int){
                ListNode *t = new ListNode(tmp->val); 
                tt->next = t; 
                tt = t; 
            }
            if(tmp->left){
                q.push(tmp->left); qint.push(tmp_int + 1); 
            }
            if(tmp->right){
                q.push(tmp->right); qint.push(tmp_int + 1); 
            }
        }  
        return ans->next; */  

    }
};