leetcode/AllNodesDistanceKinBinaryTree

All Nodes Distance K in Binary Tree

找出树中距离指定节点距离为 n 的节点

my solutions

emm…

第一种方法是制作一个映射, 其中 key 为节点值, val 为所有与 key 相邻的节点值集合.

这种方法适用于多次查询, 因为需要制作一个完整的映射表, 所以不推荐 :(

第二种是让每个节点有一个 parent, 节点便利的麻烦之处就在于他没有 parent 节点. 标准库的节点都是有 parent 节点的(除指定的 froward_list 外 = =), 足以说明有 parent 不仅对于编程, 同时对于效率也有很大提升.

但这也类似于第一种, 这种更加轻量级, 但便利寻找的时候会比第一种稍微麻烦一些.

我采用了第二种的部分概念.

仔细分析一下这个题的话, 节点相邻节点只有两种可能, 父节点和子节点. 子节点的便利非常简单, 广度优先找到同样深度的子节点就好, 问题在于父节点. 而如果找出父节点的简单规律的话, 这题也比较简单了. 假设距离为 N, 从父节点开始, 除特定子节点外的深度为 N - 1 的节点就是值的一部分, 一次类推, pp(父父)节点则是 N - 2, 直到为 0 为止, 就能遍历出所有的集.

class Solution {
public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
        stack<TreeNode*> s;
        dfs(root, s, target);

        vector<int> ret;
        TreeNode *l = s.top();
        getN(l, ret, K--);
        s.pop();
        while (K >= 0 && !s.empty()) {
            TreeNode *c = s.top()->left == l ? s.top()->right : s.top()->left;
            if (!K) {
                ret.push_back(s.top()->val);
                break;
            }
            getN(c, ret, K-- - 1);
            l = s.top();
            s.pop();
        }

        return ret;
    }

    void getN(TreeNode *n, vector<int>& vec, int d) {
        if (!n) { 
            return;
        } else if (!d) {
            vec.push_back(n->val);
            return;
        }

        vector<TreeNode*> t { n };
        while (true) {
            vector<TreeNode*> c;
            for (auto v : t) {
                if (v->left) {
                    c.push_back(v->left);
                }
                if (v->right) {
                    c.push_back(v->right);
                }
            }

            if (!--d) {
                for (auto v : c) {
                    vec.push_back(v->val);
                }

                break;
            }
            swap(c, t);
        }

        return;
    }

    bool dfs(TreeNode *n, stack<TreeNode*>& s, TreeNode *t) {
        s.push(n);
        if (!n) {
            return false;
        }

        if (n == t) {
            return true;
        }

        if (dfs(n->left, s, t)) {
            return true;
        }

        s.pop();
        if (dfs(n->right, s, t)) {
            return true;
        }

        s.pop();
        return false;
    }
};

代码丑是丑了点 = =, 不过我其他算法也没好到哪里去… (这是必要的损失么?)

the best solution

class Solution {
public:
    struct TreeNode2 {
        int val;
        TreeNode2 *left;
        TreeNode2 *right;
        TreeNode2 *ahead;
        bool checked;
        TreeNode2(int x) : val(x), left(NULL), right(NULL) ,ahead(NULL),checked(false){}
    };

    TreeNode2* target2;

    void findahead(TreeNode* node,TreeNode2* newnode,TreeNode* target){
        if (node == NULL) return;
        TreeNode2 *leftnode;
        TreeNode2 *rightnode;
        if (newnode->val ==  target->val) this->target2 = newnode;
        if (node->left != NULL) {
            leftnode = new TreeNode2(node->left->val);
            newnode->left = leftnode;
            newnode->left->ahead = newnode;
        }
        if (node->right != NULL) {
            rightnode = new TreeNode2(node->right->val);
            newnode->right = rightnode;
            newnode->right->ahead = newnode;
        }
        findahead(node->left,leftnode,target);
        findahead(node->right,rightnode,target);
    }

    void dfs(TreeNode2* node,int step,int& k,vector<int>& res){
        if (node == NULL) return;
        if (node->checked == true) return;
        node->checked = true;
        if (k == step) res.push_back(node->val);
        if (step > k) return;
        dfs(node->left,step + 1,k,res);
        dfs(node->right,step + 1,k,res);
        dfs(node->ahead,step + 1,k,res);
    }

    vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
        //constuct ahead
        vector<int> res;
        TreeNode2* newroot = new TreeNode2(root->val);
        findahead(root,newroot,target);
        dfs(this->target2,0,K,res);
        return res;
    }
};

它新建了一个节点, 其中包含 left, right, ahead 指针 :(

这会让查找变得简单, 但我并不认可这种方式 = =.