A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 863. All Nodes Distance K in Binary Tree, the solution in this repository is mainly a two pointers solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers, sliding window.
The notes already sitting in the source point us in the right direction:
- Approach 1: Annotate Parent
- time: O(N), space: O(N)
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are dfs, dfsUpDown, distanceK, subtreeAdd.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(N), space: O(N)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Approach 1: Annotate Parent
02//Runtime: 12 ms, faster than 32.60% of C++ online submissions for All Nodes Distance K in Binary Tree.
03//Memory Usage: 12.9 MB, less than 100.00% of C++ online submissions for All Nodes Distance K in Binary Tree.
04//time: O(N), space: O(N)
05/**
06 * Definition for a binary tree node.
07 * struct TreeNode {
08 * int val;
09 * TreeNode *left;
10 * TreeNode *right;
11 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
12 * };
13 */
14class Solution {
15public:
16 vector<int> ans;
17 map<TreeNode*, TreeNode*> parent;
18
19 // void dfs(TreeNode* node, int K){
20 // if(!node) return;
21 // if(K == 0){
22 // ans.push_back(node->val);
23 // return;
24 // }
25 // if(node->left){
26 // dfs(node->left, K-1);
27 // }
28 // if(node->right){
29 // dfs(node->right, K-1);
30 // }
31 // };
32
33 void dfsUpDown(TreeNode* node, TreeNode* target, int K){
34 if(!node) return;
35 if(K == 0){
36 ans.push_back(node->val);
37 return;
38 }
39 if(parent[node] && parent[node] != target){
40 /*
41 next time when parent[node] considers which path to take,
42 it will not go to "node" again
43 */
44 dfsUpDown(parent[node], node, K-1);
45 }
46 if(node->left && node->left != target){
47 /*
48 next time when node->left considers which path to take,
49 it will not go to "node" again
50 */
51 dfsUpDown(node->left, node, K-1);
52 }
53 if(node->right && node->right != target){
54 dfsUpDown(node->right, node, K-1);
55 }
56 };
57
58 vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
59 queue<TreeNode*> q;
60 TreeNode* cur;
61
62 q.push(root);
63 parent[root] = nullptr;
64
65 while(!q.empty()){
66 cur = q.front(); q.pop();
67 // if(cur == target) break;
68
69 if(cur->left){
70 parent[cur->left] = cur;
71 q.push(cur->left);
72 }
73
74 if(cur->right){
75 parent[cur->right] = cur;
76 q.push(cur->right);
77 }
78 }
79
80 //put its descendent into ans
81 dfsUpDown(target, target, K);
82
83 return ans;
84 }
85};
86
87//Approach 2: Percolate Distance
88//Runtime: 4 ms, faster than 93.76% of C++ online submissions for All Nodes Distance K in Binary Tree.
89//Memory Usage: 12.4 MB, less than 100.00% of C++ online submissions for All Nodes Distance K in Binary Tree.
90//time: O(N), space: O(N)
91/**
92 * Definition for a binary tree node.
93 * struct TreeNode {
94 * int val;
95 * TreeNode *left;
96 * TreeNode *right;
97 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
98 * };
99 */
100class Solution {
101public:
102 vector<int> ans;
103 TreeNode* target;
104 int K;
105
106 /*
107 find in the subtree rooted at node,
108 if the distance of the root and a node is K,
109 then add it into ans
110 */
111 void subtreeAdd(TreeNode* node, int dist){
112 if(node == nullptr) return;
113 // cout << node->val << ", dist: " << dist << endl;
114 if(dist == K){
115 ans.push_back(node->val);
116 }else{
117 subtreeAdd(node->left, dist+1);
118 subtreeAdd(node->right, dist+1);
119 }
120 };
121
122 //if node and connect to target, return their vertex distance
123 //else return -1
124 //vertex distance: #vertices on path from node to target
125 int dfs(TreeNode* node){
126 if(!node) return -1;
127 if(node == target){
128 subtreeAdd(node, 0);
129 return 1;
130 }
131
132 int L = dfs(node->left);
133 int R = dfs(node->right);
134 if(L != -1){
135 //we can find target in left subtree
136 if(L == K) ans.push_back(node->val);
137 //-1: vertex distance->normal distance
138 //+2: node->left to node to node->right
139 subtreeAdd(node->right, L-1+2);
140 return L-1+2;
141 }else if(R != -1){
142 if(R == K) ans.push_back(node->val);
143 subtreeAdd(node->left, R-1+2);
144 return R-1+2;
145 }
146 //cannot find target in both its left subtree nor right subtree
147 return -1;
148 };
149
150 vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
151 this->target = target;
152 this->K = K;
153 dfs(root);
154 return ans;
155 }
156};Cost
Complexity
Time
O(N), space: O(N)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.