给定一个具有不同节点的二叉树（没有两个节点具有相同的数据值）。问题是打印从根到给定节点的路径 十、 .If节点 十、 不存在，则打印“无路径”。
null
例如：
Input : 1 / 2 3 / / 4 5 6 7 x = 5Output : 1->2->5
方法： 创建一个递归函数，遍历二叉树中的不同路径以找到所需的节点 十、 .If节点 十、 如果存在，则返回true并将路径节点累加到某个数组中 arr[] .否则返回false。 以下是遍历过程中的情况：
- 如果 root=NULL ，返回false。
- 将根目录的数据推入 arr[] .
- 如果 根的数据=x ，返回true。
- if节点 十、 存在于根的左或右子树中，返回true。
- 否则请从中删除root的数据值 arr[] 返回false。
可以从其他函数访问此递归函数，以检查节点 十、 是否存在，如果存在，则可以从 arr[] .你可以定义 arr[] 全局或将其引用传递给递归函数。
C++
// C++ implementation to print the path from root // to a given node in a binary tree #include <bits/stdc++.h> using namespace std; // structure of a node of binary tree struct Node { int data; Node *left, *right; }; /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct Node* getNode( int data) { struct Node *newNode = new Node; newNode->data = data; newNode->left = newNode->right = NULL; return newNode; } // Returns true if there is a path from root // to the given node. It also populates // 'arr' with the given path bool hasPath(Node *root, vector< int >& arr, int x) { // if root is NULL // there is no path if (!root) return false ; // push the node's value in 'arr' arr.push_back(root->data); // if it is the required node // return true if (root->data == x) return true ; // else check whether the required node lies // in the left subtree or right subtree of // the current node if (hasPath(root->left, arr, x) || hasPath(root->right, arr, x)) return true ; // required node does not lie either in the // left or right subtree of the current node // Thus, remove current node's value from // 'arr'and then return false arr.pop_back(); return false ; } // function to print the path from root to the // given node if the node lies in the binary tree void printPath(Node *root, int x) { // vector to store the path vector< int > arr; // if required node 'x' is present // then print the path if (hasPath(root, arr, x)) { for ( int i=0; i<arr.size()-1; i++) cout << arr[i] << "->" ; cout << arr[arr.size() - 1]; } // 'x' is not present in the binary tree else cout << "No Path" ; } // Driver program to test above int main() { // binary tree formation struct Node *root = getNode(1); root->left = getNode(2); root->right = getNode(3); root->left->left = getNode(4); root->left->right = getNode(5); root->right->left = getNode(6); root->right->right = getNode(7); int x = 5; printPath(root, x); return 0; } |
JAVA
// Java implementation to print the path from root // to a given node in a binary tree import java.util.ArrayList; public class PrintPath { // Returns true if there is a path from root // to the given node. It also populates // 'arr' with the given path public static boolean hasPath(Node root, ArrayList<Integer> arr, int x) { // if root is NULL // there is no path if (root== null ) return false ; // push the node's value in 'arr' arr.add(root.data); // if it is the required node // return true if (root.data == x) return true ; // else check whether the required node lies // in the left subtree or right subtree of // the current node if (hasPath(root.left, arr, x) || hasPath(root.right, arr, x)) return true ; // required node does not lie either in the // left or right subtree of the current node // Thus, remove current node's value from // 'arr'and then return false arr.remove(arr.size()- 1 ); return false ; } // function to print the path from root to the // given node if the node lies in the binary tree public static void printPath(Node root, int x) { // ArrayList to store the path ArrayList<Integer> arr= new ArrayList<>(); // if required node 'x' is present // then print the path if (hasPath(root, arr, x)) { for ( int i= 0 ; i<arr.size()- 1 ; i++) System.out.print(arr.get(i)+ "->" ); System.out.print(arr.get(arr.size() - 1 )); } // 'x' is not present in the binary tree else System.out.print( "No Path" ); } public static void main(String args[]) { Node root= new Node( 1 ); root.left = new Node( 2 ); root.right = new Node( 3 ); root.left.left = new Node( 4 ); root.left.right = new Node( 5 ); root.right.left = new Node( 6 ); root.right.right = new Node( 7 ); int x= 5 ; printPath(root, x); } } // A node of binary tree class Node { int data; Node left, right; Node( int data) { this .data=data; left=right= null ; } }; //This code is contributed by Gaurav Tiwari |
Python3
# Python3 implementation to print the path from # root to a given node in a binary tree # Helper Class that allocates a new node # with the given data and None left and # right pointers. class getNode: def __init__( self , data): self .data = data self .left = self .right = None # Returns true if there is a path from # root to the given node. It also # populates 'arr' with the given path def hasPath(root, arr, x): # if root is None there is no path if ( not root): return False # push the node's value in 'arr' arr.append(root.data) # if it is the required node # return true if (root.data = = x): return True # else check whether the required node # lies in the left subtree or right # subtree of the current node if (hasPath(root.left, arr, x) or hasPath(root.right, arr, x)): return True # required node does not lie either in # the left or right subtree of the current # node. Thus, remove current node's value # from 'arr'and then return false arr.pop( - 1 ) return False # function to print the path from root to # the given node if the node lies in # the binary tree def printPath(root, x): # vector to store the path arr = [] # if required node 'x' is present # then print the path if (hasPath(root, arr, x)): for i in range ( len (arr) - 1 ): print (arr[i], end = "->" ) print (arr[ len (arr) - 1 ]) # 'x' is not present in the # binary tree else : print ( "No Path" ) # Driver Code if __name__ = = '__main__' : # binary tree formation root = getNode( 1 ) root.left = getNode( 2 ) root.right = getNode( 3 ) root.left.left = getNode( 4 ) root.left.right = getNode( 5 ) root.right.left = getNode( 6 ) root.right.right = getNode( 7 ) x = 5 printPath(root, x) # This code is contributed by PranchalK |
C#
// C# implementation to print the path from root // to a given node in a binary tree using System; using System.Collections; using System.Collections.Generic; class PrintPath { // A node of binary tree public class Node { public int data; public Node left, right; public Node( int data) { this .data = data; left = right = null ; } } // Returns true if there is a path from root // to the given node. It also populates // 'arr' with the given path public static Boolean hasPath(Node root, List< int > arr, int x) { // if root is NULL // there is no path if (root == null ) return false ; // push the node's value in 'arr' arr.Add(root.data); // if it is the required node // return true if (root.data == x) return true ; // else check whether the required node lies // in the left subtree or right subtree of // the current node if (hasPath(root.left, arr, x) || hasPath(root.right, arr, x)) return true ; // required node does not lie either in the // left or right subtree of the current node // Thus, remove current node's value from // 'arr'and then return false arr.RemoveAt(arr.Count - 1); return false ; } // function to print the path from root to the // given node if the node lies in the binary tree public static void printPath(Node root, int x) { // List to store the path List< int > arr = new List< int >(); // if required node 'x' is present // then print the path if (hasPath(root, arr, x)) { for ( int i = 0; i < arr.Count - 1; i++) Console.Write(arr[i]+ "->" ); Console.Write(arr[arr.Count - 1]); } // 'x' is not present in the binary tree else Console.Write( "No Path" ); } // Driver code public static void Main(String []args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); int x=5; printPath(root, x); } } // This code is contributed by Arnab Kundu |
Javascript
<script> // Javascript implementation to print // the path from root to a given node // in a binary tree class Node { constructor(data) { this .left = null ; this .right = null ; this .data = data; } } // Returns true if there is a path from root // to the given node. It also populates // 'arr' with the given path function hasPath(root, arr, x) { // If root is NULL // there is no path if (root == null ) return false ; // Push the node's value in 'arr' arr.push(root.data); // If it is the required node // return true if (root.data == x) return true ; // Else check whether the required node lies // in the left subtree or right subtree of // the current node if (hasPath(root.left, arr, x) || hasPath(root.right, arr, x)) return true ; // Required node does not lie either in the // left or right subtree of the current node // Thus, remove current node's value from // 'arr'and then return false arr.pop(); return false ; } // Function to print the path from root to the // given node if the node lies in the binary tree function printPath(root, x) { // ArrayList to store the path let arr = []; // If required node 'x' is present // then print the path if (hasPath(root, arr, x)) { for (let i = 0; i < arr.length - 1; i++) document.write(arr[i] + "->" ); document.write(arr[arr.length - 1]); } // 'x' is not present in the binary tree else document.write( "No Path" ); } // Driver code let root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); let x = 5; printPath(root, x); // This code is contributed by divyeshrabadiya07 </script> |
输出：
1->2->5
时间复杂性： O（n）在最坏的情况下，其中n是二叉树中的节点数。
本文由 阿尤什·焦哈里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
