leetcode 236 代码改进


1


题目链接 LeetCode 236

我遇到了的问题：在findpath这个函数中使用了dfs来找到两个节点之间的路径。但是个人觉得这种写法很不简洁（或者不是常用的写法），特别是引入了found这个变量，以及连续几个if (!found)判断语句。请问是否能对代码进行改进？

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool found = false;
    vector<TreeNode*> path;
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> p_to_root;
        vector<TreeNode*> q_to_root;

        findpath(root, p, p_to_root);
        found = false;
        findpath(root, q, q_to_root);

        int i = 0;
        int len = min(p_to_root.size(), q_to_root.size());
        while (p_to_root[i] == q_to_root[i] && i < len)
            i++;

        return p_to_root[i-1];


    }

    void findpath(TreeNode* root, TreeNode* p, vector<TreeNode*> &path){
        if (root != p){
            if (!root){
                path.push_back(root);
                return;
            }

            if (!found) path.push_back(root);
            if (!found) findpath(root->left, p, path);
            if (!found) path.pop_back();
            if (!found) findpath(root->right, p, path);
            if (!found) path.pop_back();
            return;
        }

        else {
            path.push_back(root);
            found = true;
            return;
        }
    }

};


这么写可以AC，但是希望可以改进写法，使得更加好看。谢谢！
代码优化

提问于2018-07-31 07:59
8601


3 个问答


1

采用 bool 型的递归即可解决问题，核心代码如下：

bool dfs(TreeNode *cur, TreeNode *des, vector<TreeNode*> &path_node) {
        if (cur == NULL)
            return false;
        if (cur == des) {
            path_node.push_back(cur);
            return true;
        }
        if (dfs(cur -> left, des, path_node) || dfs(cur -> right, des, path_node)) {
            path_node.push_back(cur);
            return true;
        }

        return false;
    }

dfs 的返回值代表目标结点是否在当前结点的子树中。

回答于2018-08-01 07:26
692443

1

这题最直观的写法 / 想法是
1) 如果p, q分别在r的两侧或者r是p或q中的一个, 那r就是LCA.
2) 否则, 如果p, q都在r.left 上, 就返回 LCA(r.left, p, q)
3) 否则, 返回LCA(r.right, p, q)

这个写法优化的方法是 - 不需要每次都在LCA上去测p, q是否都在r的两侧.

回答于2018-07-31 21:43
34729

0

class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==p||root==q||root==null) return root;
TreeNode n1=lowestCommonAncestor(root.left,p,q);
TreeNode n2=lowestCommonAncestor(root.right,p,q);
if(n1!=null&&n2!=null) return root;
return n1!=null?n1:n2;
}
}

回答于2018-10-22 18:22
0
返回节点就行了，这样更简洁吧，就是找左右子树种是否都有这两个节点 –  26   2018-10-22 18:26
我来回答