Dado un árbol de búsqueda binaria que consta de N Nodes distintos, la tarea es aplanar el árbol de búsqueda binaria dado para convertir el árbol en una lista de ondas. Una lista de ondas arr[0..n-1] se denomina lista de ondas si arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= … .
Ejemplos:
Entrada:
1
/ \
0 10
Salida:
0
\
10
\
1Entrada: 3
/ \
1 7
/ \ / \
0 2 5 10
Salida:
0
\
10
\
1
\
7
\
2
\
5
\
3
Enfoque: el problema dado se puede resolver mediante la observación de que el recorrido en orden del árbol de búsqueda binaria da Nodes en orden no decreciente. Por lo tanto, almacene el recorrido en orden del árbol dado de los primeros N/2 y los últimos N/2 Nodes usando el recorrido iterativo en orden del árbol y el reverso del recorrido en orden del árbol en dos pilas S1 y S2 respectivamente y la derecha puntero de Nodes en la pila para obtener la lista de ondas . Después de estos pasos, convierta todos los punteros izquierdos del árbol en NULL para aplanarlo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Tree Node Structure struct TreeNode { int data; TreeNode* right; TreeNode* left; // Constructor TreeNode(int data) { this->data = data; this->left = NULL; this->right = NULL; } }; // Function to insert nodes in the // binary tree TreeNode* insertNode(int data, TreeNode* root) { if (root == NULL) { TreeNode* node = new TreeNode(data); return node; } else if (data > root->data) { root->right = insertNode( data, root->right); } else if (data <= root->data) { root->left = insertNode( data, root->left); } // Return the root node return root; } // Function to count number of nodes int countNodes(TreeNode* root) { if (root == NULL) return 0; else return countNodes(root->left) + countNodes(root->right) + 1; } // Function to create an array // to wave array TreeNode* toWaveList(TreeNode* root) { int count = countNodes(root); vector<int> ans; // For inorder traversal stack<TreeNode*> s1; // For reverse Inorder traversal stack<TreeNode*> s2; TreeNode *root1 = root, *root2 = root; TreeNode *curr1 = NULL, *curr2 = NULL; // To store the root pointer of tree // after flattening TreeNode* head = NULL; // Flatten the tree TreeNode* temp = NULL; int l = 0; while (l++ < ceil(count / 2.0)) { // Iterative inorder traversal while (root1) { s1.push(root1); root1 = root1->left; } curr1 = s1.top(); s1.pop(); root1 = curr1->right; // Iterative reverse inorder // traversal while (root2) { s2.push(root2); root2 = root2->right; } curr2 = s2.top(); s2.pop(); root2 = curr2->left; // Condition for handling situation // where both curr1 and curr2 points // to the same data if (curr1->data == curr2->data) { temp->right = curr1; temp = temp->right; break; } // Flattening the tree if (head == NULL) { head = curr1; temp = curr1; temp->right = curr2; // temp->left = NULL temp = temp->right; } else { temp->right = curr1; temp = temp->right; temp->right = curr2; temp = temp->right; } } temp->right = NULL; // Setting all the left pointers // to NULL temp = head; while (temp) { temp->left = NULL; temp = temp->right; } return head; } // Driver Code int main() { TreeNode* root = NULL; int tree[] = { 1, 0, 10 }; for (int i = 0; i < 3; i++) { root = insertNode(tree[i], root); } // Function Call TreeNode* head = toWaveList(root); while (head) { cout << head->data << " "; head = head->right; } return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Tree Node Structure static class TreeNode { int data; TreeNode right; TreeNode left; // Constructor TreeNode(int data) { this.data = data; this.left = null; this.right = null; } }; // Function to insert nodes in the // binary tree static TreeNode insertNode(int data, TreeNode root) { if (root == null) { TreeNode node = new TreeNode(data); return node; } else if (data > root.data) { root.right = insertNode( data, root.right); } else if (data <= root.data) { root.left = insertNode( data, root.left); } // Return the root node return root; } // Function to count number of nodes static int countNodes(TreeNode root) { if (root == null) return 0; else return countNodes(root.left) + countNodes(root.right) + 1; } // Function to create an array // to wave array static TreeNode toWaveList(TreeNode root) { int count = countNodes(root); Vector<Integer> ans = new Vector<>(); // For inorder traversal Stack<TreeNode> s1 = new Stack<>(); // For reverse Inorder traversal Stack<TreeNode> s2 = new Stack<>(); TreeNode root1 = root, root2 = root; TreeNode curr1 = null, curr2 = null; // To store the root pointer of tree // after flattening TreeNode head = null; // Flatten the tree TreeNode temp = null; int l = 0; while (l++ < Math.ceil(count / 2.0)) { // Iterative inorder traversal while (root1 != null) { s1.add(root1); root1 = root1.left; } curr1 = s1.peek(); s1.pop(); root1 = curr1.right; // Iterative reverse inorder // traversal while (root2 != null) { s2.add(root2); root2 = root2.right; } curr2 = s2.peek(); s2.pop(); root2 = curr2.left; // Condition for handling situation // where both curr1 and curr2 points // to the same data if (curr1.data == curr2.data) { temp.right = curr1; temp = temp.right; break; } // Flattening the tree if (head == null) { head = curr1; temp = curr1; temp.right = curr2; // temp.left = null temp = temp.right; } else { temp.right = curr1; temp = temp.right; temp.right = curr2; temp = temp.right; } } temp.right = null; // Setting all the left pointers // to null temp = head; while (temp!=null) { temp.left = null; temp = temp.right; } return head; } // Driver Code public static void main(String[] args) { TreeNode root = null; int tree[] = { 1, 0, 10 }; for (int i = 0; i < 3; i++) { root = insertNode(tree[i], root); } // Function Call TreeNode head = toWaveList(root); while (head!=null) { System.out.print(head.data+ " "); head = head.right; } } } // This code is contributed by gauravrajput1
Javascript
<script> // Javascript program for the above approach // Tree Node Structure class TreeNode { // Constructor constructor(data) { this.data = data; this.left = null; this.right = null; } }; // Function to insert nodes in the // binary tree function insertNode(data, root) { if (root == null) { let node = new TreeNode(data); return node; } else if (data > root.data) { root.right = insertNode( data, root.right); } else if (data <= root.data) { root.left = insertNode( data, root.left); } // Return the root node return root; } // Function to count number of nodes function countNodes(root) { if (root == null) return 0; else return countNodes(root.left) + countNodes(root.right) + 1; } // Function to create an array // to wave array function toWaveList(root) { let count = countNodes(root); let ans = []; // For inorder traversal let s1 = []; // For reverse Inorder traversal let s2 = []; let root1 = root, root2 = root; let curr1 = null, curr2 = null; // To store the root pointer of tree // after flattening let head = null; // Flatten the tree let temp = null; let l = 0; while (l++ < Math.ceil(count / 2.0)) { // Iterative inorder traversal while (root1) { s1.push(root1); root1 = root1.left; } curr1 = s1[s1.length - 1]; s1.pop(); root1 = curr1.right; // Iterative reverse inorder // traversal while (root2) { s2.push(root2); root2 = root2.right; } curr2 = s2[s2.length - 1] s2.pop(); root2 = curr2.left; // Condition for handling situation // where both curr1 and curr2 points // to the same data if (curr1.data == curr2.data) { temp.right = curr1; temp = temp.right; break; } // Flattening the tree if (head == null) { head = curr1; temp = curr1; temp.right = curr2; // temp.left = null temp = temp.right; } else { temp.right = curr1; temp = temp.right; temp.right = curr2; temp = temp.right; } } temp.right = null; // Setting all the left pointers // to null temp = head; while (temp) { temp.left = null; temp = temp.right; } return head; } // Driver Code let root = null; let tree = [ 1, 0, 10 ]; for (let i = 0; i < 3; i++) { root = insertNode(tree[i], root); } // Function Call let head = toWaveList(root); while (head) { document.write(head.data +" "); head = head.right; } // This code is contributed by saurabh_jaiswal. </script>
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Tree Node Structure public class TreeNode { public int data; public TreeNode right; public TreeNode left; // Constructor public TreeNode(int data) { this.data = data; this.left = null; this.right = null; } }; // Function to insert nodes in the // binary tree static TreeNode insertNode(int data, TreeNode root) { if (root == null) { TreeNode node = new TreeNode(data); return node; } else if (data > root.data) { root.right = insertNode(data, root.right); } else if (data <= root.data) { root.left = insertNode(data, root.left); } // Return the root node return root; } // Function to count number of nodes static int countNodes(TreeNode root) { if (root == null) return 0; else return countNodes(root.left) + countNodes(root.right) + 1; } // Function to create an array // to wave array static TreeNode toWaveList(TreeNode root) { int count = countNodes(root); List<int> ans = new List<int>(); // For inorder traversal Stack<TreeNode> s1 = new Stack<TreeNode>(); // For reverse Inorder traversal Stack<TreeNode> s2 = new Stack<TreeNode>(); TreeNode root1 = root, root2 = root; TreeNode curr1 = null, curr2 = null; // To store the root pointer of tree // after flattening TreeNode head = null; // Flatten the tree TreeNode temp = null; int l = 0; while (l++ < Math.Ceiling(count / 2.0)) { // Iterative inorder traversal while (root1 != null) { s1.Push(root1); root1 = root1.left; } curr1 = s1.Peek(); s1.Pop(); root1 = curr1.right; // Iterative reverse inorder // traversal while (root2 != null) { s2.Push(root2); root2 = root2.right; } curr2 = s2.Peek(); s2.Pop(); root2 = curr2.left; // Condition for handling situation // where both curr1 and curr2 points // to the same data if (curr1.data == curr2.data) { temp.right = curr1; temp = temp.right; break; } // Flattening the tree if (head == null) { head = curr1; temp = curr1; temp.right = curr2; // temp.left = null temp = temp.right; } else { temp.right = curr1; temp = temp.right; temp.right = curr2; temp = temp.right; } } temp.right = null; // Setting all the left pointers // to null temp = head; while (temp != null) { temp.left = null; temp = temp.right; } return head; } // Driver Code public static void Main(String[] args) { TreeNode root = null; int []tree = { 1, 0, 10 }; for (int i = 0; i < 3; i++) { root = insertNode(tree[i], root); } // Function Call TreeNode head = toWaveList(root); while (head != null) { Console.Write(head.data + " "); head = head.right; } } } // This code is contributed by gauravrajput1
0 10 1
Complejidad de tiempo: O(N)
Espacio auxiliar: O(H), donde H es la altura de BST .