leetcode题解-112-路径总和

发表于 2019-12-25

题目

My way

递归实现

/**
 * 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 {
private:
    void dfs(TreeNode* root, int& pathSum, int sum, bool& res)
    {
        if (!root || res)  return ;

        pathSum += root->val;

        // 到达叶子结点时
        if (!root->left && !root->right && pathSum == sum) res = true;

        dfs(root->left, pathSum, sum, res);
        dfs(root->right, pathSum, sum, res);

        pathSum -= root->val;
    }

public:
    bool hasPathSum(TreeNode* root, int sum) 
    {
        int pathSum = 0;
        bool res = false;

        dfs(root, pathSum, sum, res);

        return res;    
    }
};

leetcode题解-113-路径总和Ⅱ

发表于 2019-12-19 | 更新于 2019-12-25

题目

My way

递归实现

/**
 * 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 {
private:
    vector<vector<int>> res;

    void dfs(TreeNode* root, int& pathSum, int sum, vector<int>& path)
    {
        if (!root)  return;

        pathSum += root->val;
        path.push_back(root->val);

        if (!root->left && !root->right && pathSum==sum)
        {
            res.push_back(path);
        }

        dfs(root->left, pathSum, sum, path);
        dfs(root->right, pathSum, sum, path);

        pathSum -= root->val;
        path.pop_back();
    }

public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) 
    {
        int pathSum = 0;
        vector<int> path;
        dfs(root, pathSum, sum, path);

        return res;    
    }
};

简单递归即可实现
使用pathSum变量来记录当前root结点上的路径和

leetcode题解-513-找树左下角的值

发表于 2019-12-19

题目

My way

dfs递归实现

/**
 * 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 {
private:
    int res = -1;
    int maxHeight = -1;
    void dfs(TreeNode* root, int h)
    {
        if (!root)  return;

        if (!root->left && !root->right)
        {
            if (h > maxHeight)
            {
                maxHeight = h;
                res = root->val;
            }
        }

        dfs(root->left, h + 1);
        dfs(root->right, h + 1);
    }
public:
    int findBottomLeftValue(TreeNode* root) 
    {
        dfs(root, 0);
        return res;
    }
};

运用2个辅助变量：

res记录要返回的结点的val
maxHeight记录要返回的结点的高度，用来确认是最深一个结点上的值

leetcode题解-671-二叉树中第二小的节点

发表于 2019-12-18 | 更新于 2019-12-19

题目

My way

dfs递归+3个辅助变量

/**
 * 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 {
private:
    int fir = INT_MAX;
    int sec = INT_MAX;
    int secIsChange = false;

    void dfs(TreeNode* root)
    {
        if (!root)  return;
        if ((root->val > fir && root->val < sec) || root->val == INT_MAX)  { sec = root->val;  secIsChange = true;}
        else if (root->val < fir)                                          { fir = root->val;  }
        dfs(root->left);
        dfs(root->right);
    }
public:
    int findSecondMinimumValue(TreeNode* root) 
    {
        dfs(root);

        return secIsChange?sec:-1;
    }
};

我这里没有利用到题目给的

每个节点仅有0个或2个节点数；
如果一个节点有2个节点数，那么这个节点的值不大于它子节点的值。

leetcode way

public int findSecondMinimumValue(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return -1;
        }

        int left = root.left.val;
        int right = root.right.val;

        if (left == root.val) {
            left = findSecondMinimumValue(root.left);
        }

        if (right == root.val) {
            right = findSecondMinimumValue(root.right);
        }

        if (left != -1 && right != -1) {
            return Math.min(left, right);
        }
        if (left != -1) {
            return left;
        }
        return right;

    }

Reference

https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/solution/ji-bai-liao-100de-javayong-hu-by-reedfan/

leetcode题解-230-二叉搜索树中第K小的元素

发表于 2019-12-18 | 更新于 2019-12-19

题目

My way

递归中序遍历，输出对应元素

/**
 * Definition for a binary tree node.
 * strzuct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    vector<int> vi;
    void dfs(TreeNode* root)
    {
        if (!root)  return ;

        dfs(root->left);
        vi.push_back(root->val);
        dfs(root->right);
    }
public:
    int kthSmallest(TreeNode* root, int k) {
        dfs(root);

        return vi[k-1];
    }
};

因为二叉搜索树的中序遍历结果是由小到大的，所以输出第k-1个元素即可

大力王way

递归，控制中序遍历到第`k-1`个元素

/**
 * 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:
    void dfs(TreeNode* root,int& res, bool& find, int& i, int k) {
        if (root == NULL || find) return;
        dfs(root->left, res, find, i, k);
        if (++i == k) {
            res = root->val;
            find = true;
            return;
        }
        dfs(root->right, res, find, i, k);
    }
    int kthSmallest(TreeNode* root, int k) {
        bool find = false;
        int res = -1;
        int i = 0;
        dfs(root, res, find, i, k);
        return res;
    }
};

References

https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/solution/c-zhong-xu-bian-li-ti-jie-by-da-li-wang/

leetcode题解-1261-在受污染的二叉树中查找元素

发表于 2019-12-18 | 更新于 2019-12-19

题目

My way

dfs遍历树+哈希表

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class FindElements {
private:
    set<int> s;
    void dfs(TreeNode* root, int val)
    {
        if (!root)  return;
        root->val = val;
        s.insert(val);

        if (root->left)     dfs(root->left, val*2+1);
        if (root->right)    dfs(root->right, val*2+2);
    }

public:
    FindElements(TreeNode* root) {
        dfs(root, 0);
    }
    
    bool find(int target) {
        if (s.count(target))    return true;
        else    return false;
    }
};

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements* obj = new FindElements(root);
 * bool param_1 = obj->find(target);
 */

leetcode题解-109-将有序数组转换为二叉搜索树

发表于 2019-12-17 | 更新于 2019-12-19

题目

My way

递归实现

/**
 * 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 {
private:
    TreeNode* helper(const vector<int>& nums, int l, int r)
    {
        if (l > r)  return nullptr;

        int mid = (r - l)/2 + l; 
        auto root = new TreeNode(nums[mid]);
        root->left = helper(nums, l, mid-1);
        root->right = helper(nums, mid+1, r);
        
        return root;
    }

public:
    TreeNode* sortedArrayToBST(vector<int>& nums) 
    {

        return !nums.size()? nullptr: helper(nums, 0, nums.size()-1);
    }
};

leetcode题解-284-顶端迭代器

发表于 2019-12-17 | 更新于 2019-12-19

题目

大力王way

// Below is the interface for Iterator, which is already defined for you.
// **DO NOT** modify the interface for Iterator.

class Iterator {
	struct Data;
	Data* data;
public:
	Iterator(const vector<int>& nums);
	Iterator(const Iterator& iter);
	virtual ~Iterator();
	// Returns the next element in the iteration.
	int next();
	// Returns true if the iteration has more elements.
	bool hasNext() const;
};


class PeekingIterator : public Iterator {
public:
    int curr;
    bool hit_end;
	PeekingIterator(const vector<int>& nums) : Iterator(nums) {
	    // Initialize any member here.
	    // **DO NOT** save a copy of nums and manipulate it directly.
	    // You should only use the Iterator interface methods.
	    hit_end = false;
        if (Iterator::hasNext()) {
            curr = Iterator::next();
        } else {
            hit_end = true;
        }
	}

    // Returns the next element in the iteration without advancing the iterator.
	int peek() {
        return curr;
	}

	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	int next() {
        if (hit_end) {
            return -1;
        }
        int res = curr;
	    if (Iterator::hasNext()) {
            curr = Iterator::next();
        } else {
            hit_end = true;
        }
        return res;
	}

	bool hasNext() const {
	    return !hit_end;
	}
};

简单修改了一下，把cur, hit_end放到private作用域里了。

// Below is the interface for Iterator, which is already defined for you.
// **DO NOT** modify the interface for Iterator.

class Iterator {
    struct Data;
	Data* data;
public:
	Iterator(const vector<int>& nums);
	Iterator(const Iterator& iter);
	virtual ~Iterator();
	// Returns the next element in the iteration.
	int next();
	// Returns true if the iteration has more elements.
	bool hasNext() const;
};


class PeekingIterator : public Iterator {
private:
    int cur;
    bool hit_end;

public:
	PeekingIterator(const vector<int>& nums) : Iterator(nums) {
	    // Initialize any member here.
	    // **DO NOT** save a copy of nums and manipulate it directly.
	    // You should only use the Iterator interface methods.
        hit_end = false;

        if (Iterator::hasNext())
        {
            cur = Iterator::next();
        }
        else
        {
            hit_end = true;
        }
	}

    // Returns the next element in the iteration without advancing the iterator.
	int peek() 
    {
        return cur;    
	}

	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	int next() 
    {
        int res = -1;
        if (hit_end)    return -1;
        res = cur;
        if (Iterator::hasNext())
        {
            cur = Iterator::next();
        }
        else
        {
            hit_end = true;
        }

        return res;
    }

	bool hasNext() const 
    {
        return !hit_end;
	}
};

总结

不能拷贝一个基类对象进行直接操作，会涉及到子类调用父类接口的一些写法：
- 这种没有加virtual的override是通过class::function_name来调用的
用cur表示最前面元素，hit_end表示是否到了尾部

leetcode题解-173-二叉搜索树迭代器

发表于 2019-12-17 | 更新于 2019-12-19

题目

windliang

队列保存了所有的节点值

java实现

class BSTIterator {

    Queue<Integer> queue = new LinkedList<>();

    public BSTIterator(TreeNode root) {
        inorderTraversal(root);
    }

    private void inorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left);
        queue.offer(root.val);
        inorderTraversal(root.right);
    }

    /** @return the next smallest number */
    public int next() {
        return queue.poll();
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !queue.isEmpty();
    }
}

C++实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
private:
    queue<int> q;

    void inOrder(TreeNode* root)
    {
        if (!root)  return;
        inOrder(root->left);
        q.push(root->val);
        inOrder(root->right);
    }

public:
    BSTIterator(TreeNode* root) 
    {
        inOrder(root);
    }
    
    /** @return the next smallest number */
    int next() 
    {
        auto front = q.front(); q.pop();
        return front;
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() 
    {
        return !q.empty();
    }
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

要控制中序遍历的进程，一个一个输出

java实现

class BSTIterator {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = null;

    public BSTIterator(TreeNode root) {
        cur = root;
    }

    /** @return the next smallest number */
    public int next() {
        int res = -1;
        while (cur != null || !stack.isEmpty()) {
            // 节点不为空一直压栈
            while (cur != null) {
                stack.push(cur);
                cur = cur.left; // 考虑左子树
            }
            // 节点为空，就出栈
            cur = stack.pop();
            res = cur.val;
            // 考虑右子树
            cur = cur.right;
            break;
        }

        return res;
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return cur != null || !stack.isEmpty();
    }
}

C++实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
private:
    stack<TreeNode*> s;
    TreeNode* cur = nullptr;
public:
    BSTIterator(TreeNode* root) 
    {
        cur = root;
    }
    
    /** @return the next smallest number */
    int next() 
    {
        int res = -1;
        while (cur || !s.empty())
        {
            while (cur != nullptr)
            {
                s.push(cur);
                cur = cur->left;
            }

            cur = s.top(); s.pop();
            res = cur->val;

            cur = cur->right;
            break;
        }

        return res;
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() {
        return cur || !s.empty();
    }
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

总结

利用 二叉搜索树 的 中序遍历 是 升序序列 的特点，可以提前将树的结构以中序遍历结果存储起来

leetcode题解-701-二叉搜索树中的插入操作

发表于 2019-12-16 | 更新于 2019-12-19

题目

My way

递归实现

/**
 * 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:
    TreeNode* insertIntoBST(TreeNode* root, int val) 
    {
        auto node = root;
        TreeNode* tmp;
        while (node)
        {
            tmp = node;
            if (node->val == val)   return root;
            if (node->val > val)    node = node->left;
            else                    node = node->right;    
        }
        if (tmp->val > val)    tmp->left = new TreeNode(val);
        else                   tmp->right = new TreeNode(val);

        return root;
    }
};

很简单的题目，就不写非递归实现了。

Bowen Peng

something about myself and my career development.

My way

递归实现

My way

递归实现

My way

dfs递归实现

My way

dfs递归+3个辅助变量

Reference

My way

递归中序遍历，输出对应元素

递归，控制中序遍历到第k-1个元素

References

My way

dfs遍历树+哈希表

My way

递归实现

总结

队列保存了所有的节点值

java实现

C++实现

要控制中序遍历的进程，一个一个输出

java实现

C++实现

总结

My way

递归实现

递归，控制中序遍历到第`k-1`个元素