• API
• FAQ
• Tools
• Archive
daily pastebin goal
53%
SHARE
TWEET

# k distance

a guest Feb 22nd, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1.     public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
2.         ParentedTreeNode parentedTreeNode = constructParentedTree(root);
3.
4.         List<Integer> distanceK = distanceK(parentedTreeNode, target.val, K);
5.
6.         return distanceK;
7.     }
8.
9.     private List<Integer> distanceK(ParentedTreeNode treeNode, int val, int k) {
10.         ParentedTreeNode target = FindTargetNode(treeNode, val);
11.         List<Integer> distanceK = distanceK(target, k);
12.         return distanceK;
13.     }
14.
15.     private List<Integer> distanceK(ParentedTreeNode target, int K) {
16.         List<Integer> result = new ArrayList<>();
17.         Queue<ParentedTreeNode> q = new LinkedList<>();
18.         Queue<Integer> qk = new LinkedList<>();
21.         while (!q.isEmpty()) {
22.             ParentedTreeNode node = q.remove();
23.             int k = qk.remove();
24.             if (k == 0) {
26.                 continue;
27.             }
28.             if (node.left != null) {
29.                 node.left.parent = null;
32.             }
33.             if (node.right != null) {
34.                 node.right.parent = null;
37.             }
38.             if (node.parent != null) {
39.                 if (node.parent.right != null && node.parent.right.val == node.val)
40.                     node.parent.right = null;
41.                 else
42.                     node.parent.left = null;
45.             }
46.         }
47.
48.         return result;
49.     }
50.
51.     private ParentedTreeNode FindTargetNode(ParentedTreeNode treeNode, int val) {
52.         Queue<ParentedTreeNode> q = new LinkedList<>();
54.         while (!q.isEmpty()) {
55.             ParentedTreeNode node = q.remove();
56.             if (node.val == val)
57.                 return node;
58.             if (node.left != null)
60.             if (node.right != null)
62.         }
63.         return null;
64.     }
65.
66.     private ParentedTreeNode constructParentedTree(TreeNode root) {
67.         Queue<TreeNode> qt = new LinkedList<>();
68.         Queue<ParentedTreeNode> qpt = new LinkedList<>();
69.
71.         ParentedTreeNode rootqpt = new ParentedTreeNode(root.val);
73.         while (!qt.isEmpty()) {
74.             TreeNode nodeT = qt.remove();
75.             ParentedTreeNode nodePT = qpt.remove();
76.             if (nodeT.left != null) {
78.                 nodePT.left = new ParentedTreeNode(nodeT.left.val);
79.                 nodePT.left.parent = nodePT;
81.             }
82.             if (nodeT.right != null) {
84.                 nodePT.right = new ParentedTreeNode(nodeT.right.val);
85.                 nodePT.right.parent = nodePT;
87.             }
88.         }
89.         return rootqpt;
90.     }
91.
92.     public static TreeNode stringToTreeNode(String input) {
93.         input = input.trim();
94.         input = input.substring(1, input.length() - 1);
95.         if (input.length() == 0) {
96.             return null;
97.         }
98.
99.         String[] parts = input.split(",");
100.         String item = parts[0];
101.         TreeNode root = new TreeNode(Integer.parseInt(item));
102.         Queue<TreeNode> nodeQueue = new LinkedList<>();
104.
105.         int index = 1;
106.         while (!nodeQueue.isEmpty()) {
107.             TreeNode node = nodeQueue.remove();
108.
109.             if (index == parts.length) {
110.                 break;
111.             }
112.
113.             item = parts[index++];
114.             item = item.trim();
115.             if (!item.equals("null")) {
116.                 int leftNumber = Integer.parseInt(item);
117.                 node.left = new TreeNode(leftNumber);
119.             }
120.
121.             if (index == parts.length) {
122.                 break;
123.             }
124.
125.             item = parts[index++];
126.             item = item.trim();
127.             if (!item.equals("null")) {
128.                 int rightNumber = Integer.parseInt(item);
129.                 node.right = new TreeNode(rightNumber);
131.             }
132.         }
133.         return root;
134.     }
135.
136.     public static String integerArrayListToString(List<Integer> nums, int length) {
137.         if (length == 0) {
138.             return "[]";
139.         }
140.
141.         String result = "";
142.         for (int index = 0; index < length; index++) {
143.             Integer number = nums.get(index);
144.             result += Integer.toString(number) + ", ";
145.         }
146.         return "[" + result.substring(0, result.length() - 2) + "]";
147.     }
148.
149.     public static String integerArrayListToString(List<Integer> nums) {
150.         return integerArrayListToString(nums, nums.size());
151.     }
152.
153.     public static void main(String[] args) throws IOException {
155.         String line;
156.         while ((line = in.readLine()) != null) {
157.             TreeNode root = stringToTreeNode(line);
159.             TreeNode target = stringToTreeNode(line);
161.             int K = Integer.parseInt(line);
162.
163.             List<Integer> ret = new AllNodesDistanceKinBinaryTree().distanceK(root, target, K);
164.
165.             String out = integerArrayListToString(ret);
166.
167.             System.out.print(out);
168.         }
169.     }
170.
171.     public class ParentedTreeNode {
172.         int val;
173.         ParentedTreeNode left;
174.         ParentedTreeNode right;
175.         ParentedTreeNode parent;
176.
177.         ParentedTreeNode(int x) {
178.             val = x;
179.         }
180.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top