leetcode题解-429-N叉树的层序遍历

发表于 2019-12-06 | 分类于刷题

题目

My way

递归实现BFS

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
private:
    void helper(vector<vector<int>>& vvi, int level, Node* root)
    {
        if (!root)  return ;

        // add new vector<int> for saving new level elements
        if (vvi.size() == level)
        {
            vvi.push_back(vector<int>());
        }

        vvi[level].push_back(root->val);
        for (auto it : root->children)
        {
            helper(vvi, level+1, it);
        }

    }
public:
    vector<vector<int>> levelOrder(Node* root) 
    {
        vector<vector<int>> vvi;
        helper(vvi, 0, root);

        return vvi;   
    }
};

手动队列BFS

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        if (!root)  return vector<vector<int>>();

        vector<vector<int>> vvi;
        deque<Node*> q;
        q.push_back(root);

        while(!q.empty())
        {
            vector<int> vi;

            int size = q.size();
            for (int i = 0; i < size; ++i)
            {
                auto front = q.front();
                q.pop_front();

                vi.push_back(front->val);
                
                for (auto& it : front->children)
                {
                    if (it) q.push_back(it);
                }
            }

            vvi.push_back(vi);
        }

        return vvi;
    }
};

leetcode题解-63-二叉树的平均值

发表于 2019-12-06 | 分类于刷题

leetcode题解-103-二叉树的锯齿形层次遍历

发表于 2019-12-05 | 更新于 2019-12-06 | 分类于刷题

题目

My way

手动BFS + 奇逆序

/**
 * 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:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (!root)  return vector<vector<int>>();

        vector<vector<int>> vvi;
        deque<TreeNode*> q;
        q.push_back(root);

        // 可以加个depth变量，depth为偶数时，[size-1, 0]来存储变量
        while(!q.empty())
        {
            vector<int> vi;

            int size = q.size();
            for (int i = 0; i < size; ++i)
            {
                auto front = q.front();
                q.pop_front();

                vi.push_back(front->val);
                if (front->left)   q.push_back(front->left);
                if (front->right)  q.push_back(front->right);
            }

            vvi.push_back(vi);
        }

        for (size_t i = 1; i < vvi.size(); ++i, ++i)
        {
            vvi[i] = vector<int>(vvi[i].rbegin(), vvi[i].rend());
        }

        return vvi;        
    }
};

加个depth变量，depth为偶数时，[size-1, 0]来存储变量 OR 插入后逆序，因为vector::insert代价是$O(N)$，所以一直从头部差，时间cost过大，或者用deque，然后用deque中元素赋值给vector

/**
 * 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:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (!root)  return vector<vector<int>>();

        vector<vector<int>> vvi;
        deque<TreeNode*> q;
        q.push_back(root);

        // 可以加个depth变量，depth为偶数时，[size-1, 0]来存储变量
        int depth = 0;
        while(!q.empty())
        {
            vector<int> vi;
            ++depth;

            int size = q.size();
            
            for (int i = 0; i < size; ++i)
            {
                auto front = q.front();
                q.pop_front();

                vi.push_back(front->val);

                if (front->left)   q.push_back(front->left);
                if (front->right)  q.push_back(front->right);
            }

            if (!depth&(depth-1))   vi = vector<int>(vi.rbegin(), vi.rend());   

            vvi.push_back(vi);
        }

        for (size_t i = 1; i < vvi.size(); ++i, ++i)
        {
            vvi[i] = vector<int>(vvi[i].rbegin(), vvi[i].rend());
        }

        return vvi;        
    }
};

递归 + 奇逆序

/**
 * 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 helper(vector<vector<int>>& vvi, int level, TreeNode* root)
    {
        if (!root)  return ;

        // add new vector<int> for saving new level elements
        if (vvi.size() == level)
        {
            vvi.push_back(vector<int>());
        }

        vvi[level].push_back(root->val);
        helper(vvi, level+1, root->left);
        helper(vvi, level+1, root->right);
    }
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
    {
        vector<vector<int>> vvi;
        helper(vvi, 0, root);

        for (size_t i = 1; i < vvi.size(); ++i, ++i)
        {
            vvi[i] = vector<int>(vvi[i].rbegin(), vvi[i].rend());
        }

        return vvi;   
    }
};

leetcode题解-107-二叉树的层次遍历Ⅱ

发表于 2019-12-05 | 更新于 2019-12-10 | 分类于刷题

题目

My way

手动队列BFS + reverse结果

/**
 * 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:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        if (!root)  return vector<vector<int>>();

        vector<vector<int>> vvi;
        deque<TreeNode*> q;
        q.push_back(root);

        while(!q.empty())
        {
            vector<int> vi;

            int size = q.size();
            for (int i = 0; i < size; ++i)
            {
                auto front = q.front();
                q.pop_front();

                vi.push_back(front->val);
                if (front->left)   q.push_back(front->left);
                if (front->right)  q.push_back(front->right);
            }

            vvi.push_back(vi);
        }

        return vector<vector<int>>(vvi.rbegin(), vvi.rend());
    }
};

递归BFS + 逆序

/**
 * 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 helper(vector<vector<int>>& vvi, int level, TreeNode* root)
    {
        if (!root)  return ;

        // add new vector<int> for saving new level elements
        if (vvi.size() == level)
        {
            vvi.push_back(vector<int>());
        }

        vvi[level].push_back(root->val);
        helper(vvi, level+1, root->left);
        helper(vvi, level+1, root->right);

    }
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) 
    {
        vector<vector<int>> vvi;
        helper(vvi, 0, root);

        return vector<vector<int>> (vvi.rbegin(), vvi.rend());   
    }
};

有没有办法遍历的时候直接逆序插入呢？？

总结

递归方式BFS实现层次遍历时，需要在vector<vector<int>>的对应层数上存储，所以在helper函数上，需要传参

References

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/er-cha-shu-ceng-ci-bian-li-c-by-huang-fu-mai-yan/

leetcode题解-102-二叉树的层次遍历

发表于 2019-12-05 | 更新于 2019-12-10 | 分类于刷题

题目

My way

手动队列BFS

/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root)  return vector<vector<int>>();

        vector<vector<int>> vvi;
        deque<TreeNode*> q;
        q.push_back(root);

        while(!q.empty())
        {
            vector<int> vi;

            int size = q.size();
            for (int i = 0; i < size; ++i)
            {
                auto front = q.front();
                q.pop_front();

                vi.push_back(front->val);
                if (front->left)   q.push_back(front->left);
                if (front->right)  q.push_back(front->right);
            }

            vvi.push_back(vi);
        }

        return vvi;
    }
};

时间:$O(N)$, 空间:$O(N)$

官方way

递归

class Solution {
    List<List<Integer>> levels = new ArrayList<List<Integer>>();

    public void helper(TreeNode node, int level) {
        // start the current level
        if (levels.size() == level)
            levels.add(new ArrayList<Integer>());

         // fulfil the current level
         levels.get(level).add(node.val);

         // process child nodes for the next level
         if (node.left != null)
            helper(node.left, level + 1);
         if (node.right != null)
            helper(node.right, level + 1);
    }
    
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return levels;
        helper(root, 0);
        return levels;
    }
}

时间:$O(N)$, 空间:$O(N)+O(logN)= O(N)$，因为递归自动压栈需要维护一个栈，故空间上常数项系数更大

/**
 * 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 helper(vector<vector<int>>& vvi, int level, TreeNode* root)
    {
        // add new vector<int> for saving new level elements
        if (vvi.size() == level)
        {
            vvi.push_back(vector<int>());
        }

        vvi[level].push_back(root->val);
        if(root->left)     helper(vvi, level+1, root->left);
        if(root->right)    helper(vvi, level+1, root->right);
    }
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        if (!root)  return vector<vector<int>>();

        vector<vector<int>> vvi;
        helper(vvi, 0, root);

        return vvi;   
    }
};

优化递归函数helper后：

/**
 * 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 helper(vector<vector<int>>& vvi, int level, TreeNode* root)
    {
        if (!root)  return ;

        // add new vector<int> for saving new level elements
        if (vvi.size() == level)
        {
            vvi.push_back(vector<int>());
        }

        vvi[level].push_back(root->val);
        helper(vvi, level+1, root->left);
        helper(vvi, level+1, root->right);
    }
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> vvi;
        helper(vvi, 0, root);

        return vvi;   
    }
};

总结

错误点：

需要提前用哨兵记住队列的长度size，否则在遍历对应层时，长度不断变大，影响结果
对入队的结点来说，只需要入队左右子树非空结点即可。
递归方式BFS实现层次遍历时，需要在vector<vector<int>>的对应层数上存储，所以在helper函数上，需要传参

Reference

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/er-cha-shu-de-ceng-ci-bian-li-by-leetcode/

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/er-cha-shu-ceng-ci-bian-li-c-by-huang-fu-mai-yan/

leetcode题解-110-平衡二叉树

发表于 2019-12-05 | 更新于 2019-12-10 | 分类于刷题

题目

/**
 * 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 helper(const TreeNode* root, int level, bool& res)
    {
        if (!root)  return level;

        int lH = helper(root->left, level + 1, res);
        if (!res)   return level;

        int rH = helper(root->right, level + 1, res);
        if (!res)   return level;

        if (abs(lH - rH) > 1)    res = false;

        return max(lH, rH);    
    }
public:
    bool isBalanced(TreeNode* root) 
    {
        bool res = true;

        helper(root, 1, res);
        return res;
    }
};

要保证返回当前结点的树高和 是否平衡。

leetcode题解-559-N叉树的最大深度

发表于 2019-12-05 | 更新于 2019-12-10 | 分类于刷题

题目

My way

递归

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    int maxDepth(Node* root) {
        if (!root)  return 0;
        if (root->children.empty())  return 1;

        vector<int> Height;
        for (auto it : root->children)
        {
            Height.push_back(maxDepth(it));
        }

        return *max_element(Height.begin(), Height.end()) + 1;
    }
};

手动压栈DFS

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    int maxDepth(Node* root) {
        if (!root)      return 0;
        if (root->children.empty()) return 1;

        stack<pair<Node*, int>> stack;
        stack.push(make_pair(root, 1));

        int max_depth = -1;
        while(!stack.empty())
        {
            auto top = stack.top().first;
            int depth = stack.top().second;
            max_depth = max(max_depth, depth);
            stack.pop();

            for (auto it : top->children)
            {
                stack.push(make_pair(it, depth+1));
            }
        } 

        return max_depth;
    }
};

层次遍历

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
int maxDepth(Node* root) 
{
    if (!root) return 0;
    queue<Node*> queue;
    queue.push(root);
    int max_depth = 0;
    while (!queue.empty()) 
    {
        max_depth++;			
        for (int size = queue.size(); size; size--) 
        {
            Node* curr = queue.front(); 
            queue.pop();

            for (Node* it : curr->children)
            {
                queue.push(it);
            }
        }
    }
    return max_depth;
}
};

leetcode题解-111-二叉树的最小深度

发表于 2019-12-05 | 更新于 2019-12-10 | 分类于刷题

题目

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:
    int minDepth(TreeNode* root) {      
        if (!root)  return 0;
        int l_depth, r_depth;
        l_depth = minDepth(root->left);
        r_depth = minDepth(root->right);

        return !(root->left) || !(root->right) ? l_depth + r_depth + 1 : min(l_depth, r_depth) + 1;
    }
};

手动压栈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 {
public:
    int minDepth(TreeNode* root) {
        stack<pair<TreeNode*, int>> stack;

        if (!root)  return 0;

        stack.push(make_pair(root, 1));

        int min_depth = INT_MAX;
        while(!stack.empty())
        {
            auto top = stack.top();
            stack.pop();

            root = top.first;
            int depth = top.second;
            if (!(root->left) && !(root->right))
            {
                min_depth = min(min_depth, depth);
            }

            if (root->left)
            {
                stack.push(make_pair(root->left, depth + 1));
            }

            if (root->right)
            {
                stack.push(make_pair(root->right, depth + 1));
            }
        }

        return min_depth;
    }
};

层次遍历

/**
 * 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:
    int minDepth(TreeNode* root) {
        if (!root)  return 0;

        deque<TreeNode*> q;

        q.push_back(root);
        int depth = 1;
        while (!q.empty())
        {
            for (int i = 0; i < q.size(); ++i)
            {
                TreeNode* top = q.front();
                q.pop_front();

                if (!(top->left) && !(top->right))    return depth;
                if (top->left)   q.push_back(top->left);
                if (top->right)  q.push_back(top->right);
            }
            ++depth;
        }
    }
};

References

https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/li-jie-zhe-dao-ti-de-jie-shu-tiao-jian-by-user7208/

总结

被情况$[1, 2]$卡住了，因为计算的树深度是指root到leaf(左右孩子为空)的深度，此时应该是2，这个case一开始通过不了
左右子树有一个为空时，则返回左右子树的深度之和 + 1即可。
- 即，省略了对于左，右子树两个子树的两次判断为一次。
- 一种代码优化结构。

leetcode题解-104-二叉树的最大深度

发表于 2019-12-04 | 更新于 2019-12-10 | 分类于刷题

题目

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:
    int maxDepth(TreeNode* root) {
        if (!root)  return 0;

        return max(maxDepth(root->left)+1, maxDepth(root->right)+1);
    }
};

时间$O(N)$仅超过51%，空间$O(log(N)) + O(N) = O(N)$超过19%，说明递归压栈吃了不少空间，尝试改成非递归。

手动压栈

class Solution {
public:

int maxDepth(TreeNode* root){
	stack<pair<TreeNode*, int>> stack;
	
	if (root)	stack.push(pair(root, 1));
	
	int depth = 0;
	while (!stack.empty())
	{
		pair<TreeNode*, int> cur = stack.top();
        stack.pop();
        root = cur.first;
        int cur_depth = cur.second;

        if (root)
        {
            depth = max(depth, cur_depth);
            stack.push(pair(root->left, cur_depth+1));
            stack.push(pair(root->right, cur_depth+1));
        }
	}

    return depth;
}
};

时间$O(N)$仅超过51%，空间$O(N)$超过50%，手动压栈节省了不少空间。

有没有时间上更优化的解法呢？

层次遍历

References

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/er-cha-shu-de-zui-da-shen-du-by-leetcode/

leetcode题解-326-3的幂

发表于 2019-12-02 | 更新于 2019-12-10 | 分类于刷题

题目

我只会第一种循环迭代，后面3种方法均出自leetcode官方题解。

1. 循环迭代

class Solution {
public:
    bool isPowerOfThree(int n) {
        if (n < 1)  return false;
        
        while (n % 3 == 0)
        {
            n /= 3;
        }

        return n == 1;
    }
};

时间: $O(log_b(n))$

空间: $O(1)$

2. 基准转换

将所有的数转化为以3为基数的数字。

public class Solution {
    public boolean isPowerOfThree(int n) {
        return Integer.toString(n, 3).matches("^10*$");
    }
}

时间: $O(log_3n)$

空间: $O(log_3n)$

3. 运算法

\[ n = 3^i i = log_3(n)i = \frac{log_b(n)}{log_b(3)} \]

public class Solution {
    public boolean isPowerOfThree(int n) {
        return (Math.log10(n) / Math.log10(3)) % 1 == 0;
    }
}

为了解决精度错误，应该设置一个较小的epsilon

1	return (Math.log(n) / Math.log(3) + epsilon) % 1 <= 2 * epsilon;

4. 整数限制

在Java中，该变量是4个byte，则最大值为$\frac{2^{32}}{2} - 1 = 2147483647$，并得到最大的3的幂为$3^{19} = 1162251467$.

若n是3的幂，则$ 3^{19} % n == 0$必成立

public class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

时间: $O(1 )$

空间: $O( 1)$

References

https://leetcode-cn.com/problems/power-of-three/solution/3de-mi-by-leetcode/

Bowen Peng

something about myself and my career development.