给定一棵二叉树和一个数字N，编写一个程序，在给定二叉树的前序遍历中找到第N个节点。 先决条件： 树遍历 例如：
null
Input: N = 4 11 / 21 31 / 41 51Output: 51Explanation: Preorder Traversal of given Binary Tree is 11 21 41 51 31, so 4th node will be 51.Input: N = 5 25 / 20 30 / / 18 22 24 32Output: 30
解决这个问题的办法是 前序遍历 在遍历给定的二叉树时跟踪访问的节点数，并在计数等于N时打印当前节点。
C++
// C++ program to find n-th node of // Preorder Traversal of Binary Tree #include <bits/stdc++.h> using namespace std; // Tree node struct Node { int data; Node *left, *right; }; // function to create new node struct Node* createNode( int item) { Node* temp = new Node; temp->data = item; temp->left = NULL; temp->right = NULL; return temp; } // function to find the N-th node in the preorder // traversal of a given binary tree void NthPreordernode( struct Node* root, int N) { static int flag = 0; if (root == NULL) return ; if (flag <= N) { flag++; // prints the n-th node of preorder traversal if (flag == N) cout << root->data; // left recursion NthPreordernode(root->left, N); // right recursion NthPreordernode(root->right, N); } } // Driver code int main() { // construction of binary tree struct Node* root = createNode(25); root->left = createNode(20); root->right = createNode(30); root->left->left = createNode(18); root->left->right = createNode(22); root->right->left = createNode(24); root->right->right = createNode(32); // nth node int N = 6; // prints n-th found found NthPreordernode(root, N); return 0; } |
JAVA
// Java program to find n-th node of // Preorder Traversal of Binary Tree class GFG { // Tree node static class Node { int data; Node left, right; }; // function to create new node static Node createNode( int item) { Node temp = new Node(); temp.data = item; temp.left = null ; temp.right = null ; return temp; } static int flag = 0 ; // function to find the N-th node in the preorder // traversal of a given binary tree static void NthPreordernode(Node root, int N) { if (root == null ) return ; if (flag <= N) { flag++; // prints the n-th node of preorder traversal if (flag == N) System.out.print( root.data); // left recursion NthPreordernode(root.left, N); // right recursion NthPreordernode(root.right, N); } } // Driver code public static void main(String args[]) { // construction of binary tree Node root = createNode( 25 ); root.left = createNode( 20 ); root.right = createNode( 30 ); root.left.left = createNode( 18 ); root.left.right = createNode( 22 ); root.right.left = createNode( 24 ); root.right.right = createNode( 32 ); // nth node int N = 6 ; // prints n-th found found NthPreordernode(root, N); } } // This code contributed by Arnab Kundu |
Python3
# Python program to find n-th node of # Preorder Traversal of Binary Tree class createNode(): def __init__( self , data): self .data = data self .left = None self .right = None # function to find the N-th node in the preorder # traversal of a given binary tree flag = [ 0 ] def NthPreordernode(root, N): if (root = = None ): return if (flag[ 0 ] < = N): flag[ 0 ] + = 1 # prints the n-th node of preorder traversal if (flag[ 0 ] = = N): print (root.data) # left recursion NthPreordernode(root.left, N) # right recursion NthPreordernode(root.right, N) # Driver code if __name__ = = '__main__' : # construction of binary tree root = createNode( 25 ) root.left = createNode( 20 ) root.right = createNode( 30 ) root.left.left = createNode( 18 ) root.left.right = createNode( 22 ) root.right.left = createNode( 24 ) root.right.right = createNode( 32 ) # nth node N = 6 # prints n-th found found NthPreordernode(root, N) # This code is contributed by SHUBHAMSINGH10 |
C#
// C# program to find n-th node of // Preorder Traversal of Binary Tree using System; class GFG { // Tree node public class Node { public int data; public Node left, right; }; // function to create new node static Node createNode( int item) { Node temp = new Node(); temp.data = item; temp.left = null ; temp.right = null ; return temp; } static int flag = 0; // function to find the N-th node in the preorder // traversal of a given binary tree static void NthPreordernode(Node root, int N) { if (root == null ) return ; if (flag <= N) { flag++; // prints the n-th node of preorder traversal if (flag == N) Console.Write( root.data); // left recursion NthPreordernode(root.left, N); // right recursion NthPreordernode(root.right, N); } } // Driver code public static void Main(String []args) { // construction of binary tree Node root = createNode(25); root.left = createNode(20); root.right = createNode(30); root.left.left = createNode(18); root.left.right = createNode(22); root.right.left = createNode(24); root.right.right = createNode(32); // nth node int N = 6; // prints n-th found found NthPreordernode(root, N); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to find n-th node of // Preorder Traversal of Binary Tree // Tree node class Node { constructor() { this .data = 0; this .left = null ; this .right = null ; } }; // function to create new node function createNode(item) { var temp = new Node(); temp.data = item; temp.left = null ; temp.right = null ; return temp; } var flag = 0; // function to find the N-th node in the preorder // traversal of a given binary tree function NthPreordernode(root, N) { if (root == null ) return ; if (flag <= N) { flag++; // prints the n-th node of preorder traversal if (flag == N) document.write( root.data); // left recursion NthPreordernode(root.left, N); // right recursion NthPreordernode(root.right, N); } } // Driver code // construction of binary tree var root = createNode(25); root.left = createNode(20); root.right = createNode(30); root.left.left = createNode(18); root.left.right = createNode(22); root.right.left = createNode(24); root.right.right = createNode(32); // nth node var N = 6; // prints n-th found found NthPreordernode(root, N); // This code is contributed by famously. </script> |
输出：
24
时间复杂性： O（n），其中n是给定二叉树中的节点数。 辅助空间： O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
