给定一棵二叉树，将其展平成一个链表。展平后，每个节点的左侧应指向NULL，右侧应按级别顺序包含下一个节点。
null
实例 :
Input: 1 / 2 5 / 3 4 6Output: 1 2 3 4 5 6Input: 1 / 3 4 / 2 5Output: 1 3 4 2 5
方法： 本文已经讨论了一种使用递归的方法 以前的职位 .这种方法暗示了使用堆栈对二叉树进行预序遍历。在这个遍历过程中，每次在堆栈中推送一个右子对象时，右子对象就等于左子对象，左子对象就等于NULL。如果节点的右子节点变为NULL，则堆栈将弹出，右子节点将成为堆栈中弹出的值。重复上述步骤，直到堆栈的大小为零或根为空。
以下是上述方法的实施情况：
C++
// C++ program to flatten the linked // list using stack | set-2 #include <iostream> #include <stack> using namespace std; struct Node { int key; Node *left, *right; }; /* utility that allocates a new Node with the given key */ Node* newNode( int key) { Node* node = new Node; node->key = key; node->left = node->right = NULL; return (node); } // To find the inorder traversal void inorder( struct Node* root) { // base condition if (root == NULL) return ; inorder(root->left); cout << root->key << " " ; inorder(root->right); } // Function to convert binary tree into // linked list by altering the right node // and making left node point to NULL Node* solution(Node* A) { // Declare a stack stack<Node*> st; Node* ans = A; // Iterate till the stack is not empty // and till root is Null while (A != NULL || st.size() != 0) { // Check for NULL if (A->right != NULL) { st.push(A->right); } // Make the Right Left and // left NULL A->right = A->left; A->left = NULL; // Check for NULL if (A->right == NULL && st.size() != 0) { A->right = st.top(); st.pop(); } // Iterate A = A->right; } return ans; } // Driver Code int main() { /* 1 / 2 5 / 3 4 6 */ // Build the tree Node* root = newNode(1); root->left = newNode(2); root->right = newNode(5); root->left->left = newNode(3); root->left->right = newNode(4); root->right->right = newNode(6); // Call the function to // flatten the tree root = solution(root); cout << "The Inorder traversal after " "flattening binary tree " ; // call the function to print // inorder after flattening inorder(root); return 0; return 0; } |
JAVA
// Java program to flatten the linked // list using stack | set-2 import java.util.Stack; class GFG { static class Node { int key; Node left, right; } /* utility that allocates a new Node with the given key */ static Node newNode( int key) { Node node = new Node(); node.key = key; node.left = node.right = null ; return (node); } // To find the inorder traversal static void inorder(Node root) { // base condition if (root == null ) return ; inorder(root.left); System.out.print(root.key + " " ); inorder(root.right); } // Function to convert binary tree into // linked list by altering the right node // and making left node point to null static Node solution(Node A) { // Declare a stack Stack<Node> st = new Stack<>(); Node ans = A; // Iterate till the stack is not empty // and till root is Null while (A != null || st.size() != 0 ) { // Check for null if (A.right != null ) { st.push(A.right); } // Make the Right Left and // left null A.right = A.left; A.left = null ; // Check for null if (A.right == null && st.size() != 0 ) { A.right = st.peek(); st.pop(); } // Iterate A = A.right; } return ans; } // Driver Code public static void main(String[] args) { /* 1 / 2 5 / 3 4 6 */ // Build the tree Node root = newNode( 1 ); root.left = newNode( 2 ); root.right = newNode( 5 ); root.left.left = newNode( 3 ); root.left.right = newNode( 4 ); root.right.right = newNode( 6 ); // Call the function to // flatten the tree root = solution(root); System.out.print( "The Inorder traversal after " + "flattening binary tree " ); // call the function to print // inorder after flattening inorder(root); } } // This code has been contributed by 29AjayKumar |
Python3
# Python3 program to flatten the linked # list using stack | set-2 class Node: def __init__( self , key): self .key = key self .left = None self .right = None # Utility that allocates a new Node # with the given key def newNode(key): node = Node(key) node.key = key node.left = node.right = None return (node) # To find the inorder traversal def inorder(root): # Base condition if (root = = None ): return inorder(root.left) print (root.key, end = ' ' ) inorder(root.right) # Function to convert binary tree into # linked list by altering the right node # and making left node point to None def solution(A): # Declare a stack st = [] ans = A # Iterate till the stack is not empty # and till root is Null while (A ! = None or len (st) ! = 0 ): # Check for None if (A.right ! = None ): st.append(A.right) # Make the Right Left and # left None A.right = A.left A.left = None # Check for None if (A.right = = None and len (st) ! = 0 ): A.right = st[ - 1 ] st.pop() # Iterate A = A.right return ans # Driver Code if __name__ = = '__main__' : ''' 1 / 2 5 / 3 4 6 ''' # Build the tree root = newNode( 1 ) root.left = newNode( 2 ) root.right = newNode( 5 ) root.left.left = newNode( 3 ) root.left.right = newNode( 4 ) root.right.right = newNode( 6 ) # Call the function to # flatten the tree root = solution(root) print ( "The Inorder traversal after " "flattening binary tree " , end = '') # Call the function to print # inorder after flattening inorder(root) # This code is contributed by rutvik_56 |
C#
// C# program to flatten the linked // list using stack | set-2 using System; using System.Collections.Generic; class GFG { public class Node { public int key; public Node left, right; } /* utility that allocates a new Node with the given key */ static Node newNode( int key) { Node node = new Node(); node.key = key; node.left = node.right = null ; return (node); } // To find the inorder traversal static void inorder(Node root) { // base condition if (root == null ) return ; inorder(root.left); Console.Write(root.key + " " ); inorder(root.right); } // Function to convert binary tree into // linked list by altering the right node // and making left node point to null static Node solution(Node A) { // Declare a stack Stack<Node> st = new Stack<Node>(); Node ans = A; // Iterate till the stack is not empty // and till root is Null while (A != null || st.Count != 0) { // Check for null if (A.right != null ) { st.Push(A.right); } // Make the Right Left and // left null A.right = A.left; A.left = null ; // Check for null if (A.right == null && st.Count != 0) { A.right = st.Peek(); st.Pop(); } // Iterate A = A.right; } return ans; } // Driver Code public static void Main(String[] args) { /* 1 / 2 5 / 3 4 6 */ // Build the tree Node root = newNode(1); root.left = newNode(2); root.right = newNode(5); root.left.left = newNode(3); root.left.right = newNode(4); root.right.right = newNode(6); // Call the function to // flatten the tree root = solution(root); Console.Write( "The Inorder traversal after " + "flattening binary tree " ); // call the function to print // inorder after flattening inorder(root); } } // This code contributed by Rajput-Ji |
Javascript
<script> // Javascript program to flatten the linked // list using stack | set-2 class Node { constructor() { this .key = 0; this .left = null ; this .right = null ; } } /* utility that allocates a new Node with the given key */ function newNode(key) { var node = new Node(); node.key = key; node.left = node.right = null ; return (node); } // To find the inorder traversal function inorder( root) { // base condition if (root == null ) return ; inorder(root.left); document.write(root.key + " " ); inorder(root.right); } // Function to convert binary tree into // linked list by altering the right node // and making left node point to null function solution(A) { // Declare a stack var st = []; var ans = A; // Iterate till the stack is not empty // and till root is Null while (A != null || st.length != 0) { // Check for null if (A.right != null ) { st.push(A.right); } // Make the Right Left and // left null A.right = A.left; A.left = null ; // Check for null if (A.right == null && st.length != 0) { A.right = st[st.length-1]; st.pop(); } // Iterate A = A.right; } return ans; } // Driver Code /* 1 / 2 5 / 3 4 6 */ // Build the tree var root = newNode(1); root.left = newNode(2); root.right = newNode(5); root.left.left = newNode(3); root.left.right = newNode(4); root.right.right = newNode(6); // Call the function to // flatten the tree root = solution(root); document.write( "The Inorder traversal after " + "flattening binary tree " ); // call the function to print // inorder after flattening inorder(root); // This code is contributed by famously. </script> |
输出：
The Inorder traversal after flattening binary tree 1 2 3 4 5 6
时间复杂性： O（N） 辅助空间： O（对数N）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
