Отладка обхода порядка двоичного дерева - PullRequest
Новая
       7

Отладка обхода порядка двоичного дерева

0 голосов
/ 14 июня 2019

У меня есть это двоичное дерево 

    3
   / \
  9  20
    /  \
   15   7

Я хочу напечатать обход уровня в этом формате 

[
  [3],
  [9,20],
  [15,7]
]

поэтому я написал этот код, используя очередь и два списка 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        List<Integer> list=new ArrayList<>();
        List<List<Integer>> res=new LinkedList<>();
        if(root!=null)
        {
            queue.add(root);
        }

        while(!queue.isEmpty())
        {
            int size=queue.size();
            for(int i=0;i<size;i++)
            {

            TreeNode tempNode=queue.poll();
            list.add(tempNode.val);
            if(tempNode.left!=null)
                queue.add(tempNode.left);
            if(tempNode.right!=null)
                queue.add(tempNode.right);
            }
            res.add(list);
            list.clear();

        }

        return res;

    }
}

но когда я проверяю вывод, он возвращает 

[[],[],[]]

Я потратил более 1 часа на устранение проблемы, и я убежден, что мой код правильный (а это не так!) Я не знаю, что очищает список res после того, как я добавляю в него данные. пожалуйста, помогите мне исправить ошибку.

Я считаю, что list.clear () также очищает добавленный элемент списка в разрешении.

это так, тогда предположим 

x=34;
list.add(x);
x=45;
System.out.println(list); // it will still print [34]

, но с использованием списка списка и после добавления элемента к нему, а также при изменении внутреннего списка .. он также изменяет ваш список списка. почему? 

int x=3;
li.add(x);
x=45;
res.add(li);
System.out.println(li);
li.remove(0);
li.add(23);
System.out.println(res);

Ответы [ 2 ]

1 голос
/ 14 июня 2019

Это происходит потому, что вы манипулируете объектом, это не происходит с примитивными типами

Вы используете один экземпляр list после добавлениясписок во внешнем списке, вы все еще манипулируете тем же, вы всегда ссылаетесь на тот же List экземпляр

Вы добавляете его несколько раз во внешний список иочистите его, вам нужно создавать новый экземпляр на каждой итерации: 

while(!queue.isEmpty()){
    int size = queue.size();
    for(int i=0 ; i<size;i++){
        TreeNode tempNode = queue.poll();
        list.add(tempNode.val);
        if(tempNode.left!=null)
            queue.add(tempNode.left);
        if(tempNode.right!=null)
            queue.add(tempNode.right);
    }
    res.add(list);
    list = new ArrayList<>();
}
0 голосов
/ 23 июля 2019

мой рабочий код в c ++ с использованием обхода порядка уровней

вывод: 

[
  [ 10 ],
  [ 11  9 ],
  [ 7  12  15  8 ],
  [ 13  14  16  18 ],
]

код: 

#include <bits/stdc++.h> 
using namespace std; 


struct node{
    int key;
    struct node *left;
    struct node *right;
};


struct node *newnode(int key){
    struct node *Node= new node;
    Node->key=key;
    Node->left=NULL;
    Node->right=NULL;
    return Node;
}

void printNestedList(list<list<int> > nested_list) 
{ 
    cout << "[\n"; 

    list<list<int> >::iterator nested_list_itr; 

    for (nested_list_itr = nested_list.begin(); 
         nested_list_itr != nested_list.end(); 
         ++nested_list_itr) { 

        cout << "  ["; 

        list<int>::iterator single_list_itr; 

        list<int>& single_list_pointer = *nested_list_itr; 

        for (single_list_itr = single_list_pointer.begin(); 
             single_list_itr != single_list_pointer.end(); 
             single_list_itr++) { 
            cout << " " << *single_list_itr << " "; 
        } 
        cout << "],\n"; 
    } 
    cout << "]"; 
} 



void levelorder_traversal(struct node *temp){

    int l=1,level=1; 
    pair <struct node *, int> p;
    queue<pair <struct node *, int> > q;
    q.push(make_pair(temp, l));


    list<list<int> > nested_list; 
    list<int> single_list; 

    single_list.push_back(temp->key); 

    while(!q.empty()){

        struct node *temp= q.front().first;
        l= q.front().second;
        q.pop();

        if(temp->left){
            p = make_pair(temp->left, (l+1));
            q.push(p);

            if(l+1>level){
                nested_list.push_back(single_list);
                single_list.erase(single_list.begin(),single_list.end());
                level++;
            }
            single_list.push_back(temp->left->key);     
        }

        if(temp->right){
            p = make_pair(temp->right, (l+1));
            q.push(p);

            if(l+1>level){
                nested_list.push_back(single_list);
                single_list.erase(single_list.begin(),single_list.end());
                level++;
            }
            single_list.push_back(temp->right->key);            
        }

        if(q.empty()){
            nested_list.push_back(single_list);
        }   
    }
    cout<<endl;

    printNestedList(nested_list);     
}


int main(){

    struct node* root = newnode(10); 
    root->left = newnode(11); 
    root->left->left = newnode(7); 
    root->left->right = newnode(12); 
    root->right = newnode(9); 
    root->right->left = newnode(15); 
    root->right->right = newnode(8); 
    root->left->left->left = newnode(13); 
    root->left->left->right = newnode(14); 
    root->left->right->left = newnode(16); 
    root->left->right->right = newnode(18); 

    levelorder_traversal(root);
}
...