AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

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
wanting
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
wzc1995
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
A美国老哈家鸡盖…
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
26
0

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


我来回答
你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息