問題描述

給定一個二叉樹（具有根結(jié)點 root）， 一個目標結(jié)點 target 媒抠，和一個整數(shù)值 K 祟蚀。
返回到目標結(jié)點 target 距離為 K 的所有結(jié)點的值的列表。 答案可以以任何順序返回魄鸦。

Example

輸入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
輸出：[7,4,1]
解釋：
所求結(jié)點為與目標結(jié)點（值為 5）距離為 2 的結(jié)點，
值分別為 7癣朗，4拾因，以及 1

Note

• 給定的樹是非空的。
• 樹上的每個結(jié)點都具有唯一的值 0 <= node.val <= 500 旷余。
• 目標結(jié)點 target 是樹上的結(jié)點绢记。
• 0 <= K <= 1000.

題目鏈接：863. 二叉樹中所有距離為 K 的結(jié)點 (難度:中等)

思路

從題目的表述可以看出，這個題目需要我們做兩件事情：

1. 從 root 向下找到所有距離為 k 的節(jié)點
2. 從 root 的祖先節(jié)點 father 中正卧，找到所有位于 father 另一子樹的與 root 距離為 k - x 的節(jié)點(其中 root 與 father 的距離為 x)蠢熄。

對于第一個任務(wù)，直接采用先序遍歷即可炉旷。對于第二個任務(wù)签孔，同樣采用先序遍歷，但在回溯時會返回 root 與 father 之間的距離 x窘行，然后再在 father 的另一棵子樹中搜索距離為 k - x 的所有節(jié)點

代碼

class Solution {
public:
    typedef pair<bool, int> pair;
    vector<int> ans;
    void search_in_child(TreeNode* root, int K){
        if(root == NULL)  return;
        if(K == 0){
            ans.push_back(root->val);
            return;
        }
        search_in_child(root->left, K - 1);
        search_in_child(root->right, K - 1);
    }
    int search_in_parent(TreeNode* root, TreeNode* target, int K){
        if(root == NULL){
            return 0;
        }
        if(root == target){
            return 1;
        }
        int l_dis = search_in_parent(root->left, target, K);
        if(l_dis){
            if(l_dis == K){
                ans.push_back(root->val);
            }else{
                search_in_child(root->right, K - 1 - l_dis);
            }
            return l_dis + 1;
        }
        int r_dis = search_in_parent(root->right, target, K);
        if(r_dis){
            if(r_dis == K){
                ans.push_back(root->val);
            }else{
                search_in_child(root->left,K - 1 - r_dis);
            }
            return r_dis + 1;
        }
        return 0;
    }
    vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
        search_in_child(target,K);
        search_in_parent(root, target, K);
        return ans;
    }
};

執(zhí)行結(jié)果： 4 ms, 12.6 MB