首页 > 代码库 > Print all nodes at distance k from a given node
Print all nodes at distance k from a given node
Given a binary tree, a target node in the binary tree, and an integer value k, print all the nodes that are at distance k from the given target node. No parent pointers are available
Consider the tree shown in diagram
Input: target = pointer to node with data 8.
root = pointer to node with data 20.
k = 2.
Output : 10 14 22
If target is 14 and k is 3, then output should be "4 20"
from: http://www.geeksforgeeks.org/print-nodes-distance-k-given-node-binary-tree/
与该点相距k的点,分两种:
1. 在k的子树;
2. k回溯到前第d个点,然后从该点往左子树或者右子树求第k-d个点。
中序遍历,记录和target的距离。
每个点最多会被访问两次。所以还是O(n).
Print all nodes at distance k from a given node
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。