Een binaire boom omkeren in Java
1. Overzicht
Het omkeren van een binaire boom is een van de problemen die we tijdens een technisch interview kunnen oplossen.
In deze korte handleiding zien we een aantal verschillende manieren om dit probleem op te lossen.
2. Binaire boom
Een binaire boom is een datastructuur waarin elk element maximaal twee kinderen heeft, die het linkerkind en het rechterkind worden genoemd. Het bovenste element van de boom is het wortelknooppunt, terwijl de kinderen zijn de innerlijke knooppunten.
Echter, als een knoop geen kind heeft, wordt het een blad genoemd.
Dat gezegd hebbende, laten we ons object maken dat een knooppunt vertegenwoordigt:
openbare klasse TreeNode {privé int waarde; privé TreeNode rightChild; privé TreeNode leftChild; // Getters en setters}Laten we vervolgens onze stamboom maken die we in onze voorbeelden zullen gebruiken:
TreeNode leaf1 = nieuwe TreeNode (1); TreeNode leaf2 = nieuwe TreeNode (3); TreeNode leaf3 = nieuwe TreeNode (6); TreeNode leaf4 = nieuwe TreeNode (9); TreeNode nodeRight = nieuwe TreeNode (7, leaf3, leaf4); TreeNode nodeLeft = nieuwe TreeNode (2, leaf1, leaf2); TreeNode root = nieuwe TreeNode (4, nodeLeft, nodeRight); In de vorige methode hebben we de volgende structuur gemaakt:
Door de boom van links naar rechts om te draaien, krijgen we de volgende structuur:
3. De binaire structuur omkeren
3.1. Recursieve methode
In het eerste voorbeeld we zullen recursie gebruiken om de boom om te keren.
Allereerst, we noemen onze methode met behulp van de wortel van de boom, dan passen we deze respectievelijk toe op de linker- en rechterkinderen totdat we de bladeren van de boom bereiken:
openbare ongeldige reverseRecursive (TreeNode treeNode) {if (treeNode == null) {return; } TreeNode temp = treeNode.getLeftChild (); treeNode.setLeftChild (treeNode.getRightChild ()); treeNode.setRightChild (temp); reverseRecursive (treeNode.getLeftChild ()); reverseRecursive (treeNode.getRightChild ()); }3.2. Iteratieve methode
In het tweede voorbeeld we zullen de boom omkeren met een iteratieve benadering. Daarom, we gaan een LinkedList, die we initialiseren met de wortel van onze boom.
Dan, voor elk knooppunt dat we uit de lijst peilen, voegen we de onderliggende punten toe aan die lijst voordat we ze permuteren.
We blijven het LinkedList totdat we de bladeren van de boom bereiken:
openbare ongeldige reverseIterative (TreeNode treeNode) {lijst wachtrij = nieuwe LinkedList (); if (treeNode! = null) {queue.add (treeNode); } while (! queue.isEmpty ()) {TreeNode node = queue.poll (); if (node.getLeftChild ()! = null) {queue.add (node.getLeftChild ()); } if (node.getRightChild ()! = null) {queue.add (node.getRightChild ()); } TreeNode temp = node.getLeftChild (); node.setLeftChild (node.getRightChild ()); node.setRightChild (temp); }}4. Conclusie
In dit korte artikel hebben we de twee manieren onderzocht om een binaire boom om te keren. We zijn begonnen met een recursieve methode om het om te keren. Vervolgens gebruikten we een iteratieve manier om hetzelfde resultaat te bereiken.
De volledige broncode van deze voorbeelden en unit-testcases is te vinden op Github.
