题解 | #找到搜索二叉树中两个错误的节点#

找到搜索二叉树中两个错误的节点

http://www.nowcoder.com/practice/4582efa5ffe949cc80c136eeb78795d6

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return int整型vector
     */
    void dfs(TreeNode* root, vector<int>& vec) {
        if(!root)
            return;
        dfs(root->left, vec);
        vec.push_back(root->val);
        dfs(root->right, vec);
    }
    vector<int> findError(TreeNode* root) {
        // write code here
        vector<int> res, tmp;
        dfs(root, res);
        // res作为遍历树的顺序列表
        if(res.size() < 2)
            return tmp;
        int pre = res[0];
        for(int i = 0; i < res.size() - 1; i++) {
            if(res[i] > res[i+1]) {
                tmp.push_back(res[i]);
                int j = i + 1;
                while(j < res.size() && res[j] < res[i])
                    j++;
                tmp.push_back(res[j-1]);
                break;
            }
        }
        swap(tmp[0], tmp[1]);
        return tmp;
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-10 12:05
点赞 评论 收藏
分享
自学java狠狠赚一...:骗你点star的,港卵公司,记得把star收回去
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务