leetcode题解-897-递增顺序查找树

发表于 2020-01-02

题目

My way

中序遍历用vector存储结果 + 按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 {
private:
    void inOrder(TreeNode* root, vector<int>& vi)
    {
        if (!root)  return ;

        inOrder(root->left, vi);
        vi.push_back(root->val);
        inOrder(root->right, vi);
    }
public:
    TreeNode* increasingBST(TreeNode* root) 
    {
        vector<int> vi;
        inOrder(root, vi);

        TreeNode* res = new TreeNode(0);
        TreeNode* cur = res;

        for (auto& it: vi)
        {
            cur->right = new TreeNode(it);
            cur = cur->right;
        }

        return res->right;
    }
};

就地拼接 + 不使用额外空间复杂度

/**
 * 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* cur;
    void inOrder(TreeNode* node)
    {
        if (!node)  return;

        inOrder(node->left);
        
        node->left = nullptr;
        cur->right = node;
        cur = node;

        inOrder(node->right);
    }

public:
    TreeNode* increasingBST(TreeNode* root) 
    {
        TreeNode* res = new TreeNode(0);
        cur = res;
        inOrder(root);

        return res->right;
    }
};

Reference

https://leetcode-cn.com/problems/increasing-order-search-tree/solution/di-zeng-shun-xu-cha-zhao-shu-by-leetcode/

leetcode题解-979-在二叉树中分配硬币

发表于 2020-01-02

题目

官方way

class Solution {
    int ans;
    public int distributeCoins(TreeNode root) {
        ans = 0;
        dfs(root);
        return ans;
    }

    public int dfs(TreeNode node) {
        if (node == null) return 0;
        int L = dfs(node.left);
        int R = dfs(node.right);
        ans += Math.abs(L) + Math.abs(R);
        return node.val + L + R - 1;
    }
}

一种抽象的思维：

抽象：硬币数 \(\rightarrow\) 负载量，考虑成: \(一个节点的负载量 = abs(硬币数-1)\)
节点间的硬币的移动数量: abs(dfs(node->left)) + abs(dfs(node->right))

Reference

https://leetcode-cn.com/problems/distribute-coins-in-binary-tree/solution/zai-er-cha-shu-zhong-fen-pei-ying-bi-by-leetcode/

leetcode题解-222-完全二叉树的节点个数

发表于 2020-01-02

题目

Wanglihao way

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
           return 0;
        } 
        int left = countLevel(root.left);
        int right = countLevel(root.right);
        if(left == right){
            return countNodes(root.right) + (1<<left);
        }else{
            return countNodes(root.left) + (1<<right);
        }
    }
    private int countLevel(TreeNode root){
        int level = 0;
        while(root != null){
            level++;
            root = root.left;
        }
        return level;
    }
}

利用了完全二叉树定义：

它是一棵空树或者它的叶子节点只出在最后两层，若最后一层不满则叶子节点只在最左侧。
1. left == right. 说明左子树一定是满二叉树，因为节点已经填充到右子树了，左子树必然填满了。所以左子树的节点总数我们可以直接得到，是\(2^{left }- 1\)，加上当前这个root节点，则正好是\(2^{left}\)。再对右子树进行递归统计。
2. left != right. 说明此时到了树的倒数第二层了，且倒数第二层已经满了，可以直接得到右子树的节点个数。同理，右子树节点+root节点，总数为\(2^{right}\). 再对左子树进行递归查找。

总结

完全二叉树的定义引申出通过对左右孩子的判断，来得到对于节点个数的计算：
- left == right.
  
  说明左子树一定是满二叉树，因为节点已经填充到右子树了，左子树必然填满了。所以左子树的节点总数我们可以直接得到，是\(2^{left }- 1\)，加上当前这个root节点，则正好是\(2^{left}\)。再对右子树进行递归统计。
- left != right.
  
  说明此时到了树的倒数第二层了，且倒数第二层已经满了，可以直接得到右子树的节点个数。同理，右子树节点+root节点，总数为\(2^{right}\). 再对左子树进行递归查找。
- 完全二叉树的高度：
  
  树的高度 = 树的最左节点的深度
简单的位运算：
- \(2^{left} = (1 < < left)\)

References

https://leetcode-cn.com/problems/count-complete-tree-nodes/

位运算的总结

发表于 2019-12-30 | 分类于位运算

之后会再专门总结，目前就先这样挖个坑。

Referece

https://blog.csdn.net/shimazhuge/article/details/24913417

leetcode题解-965-单值二叉树

发表于 2019-12-30 | 分类于树的遍历

题目

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 val;
    bool isUT = true;

    void dfs(TreeNode* root)
    {
        if (!root || !isUT)  return;

        isUT = (val == root->val ? true : false);

        dfs(root->left);
        dfs(root->right);
    }

public:
    bool isUnivalTree(TreeNode* root) 
    {
        val = root->val;

        dfs(root);

        return isUT;    
    }
};

leetcode题解-114-二叉树展开为链表

发表于 2019-12-30 | 分类于后序遍历

题目

windliang way

对左右子树进行拼接的过程

    1
   / \
  2   5
 / \   \
3   4   6

//将 1 的左子树插入到右子树的地方
    1
     \
      2         5
     / \         \
    3   4         6        
//将原来的右子树接到左子树的最右边节点
    1
     \
      2          
     / \          
    3   4  
         \
          5
           \
            6
            
 //将 2 的左子树插入到右子树的地方
    1
     \
      2          
       \          
        3       4  
                 \
                  5
                   \
                    6   
        
 //将原来的右子树接到左子树的最右边节点
    1
     \
      2          
       \          
        3      
         \
          4  
           \
            5
             \
              6         
  
  ......

/**
 * 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 flatten(TreeNode* root) 
    {
        while (root)
        {
            // root->left is nullptr
            if (!root->left)
            {
                root = root->right;
            }
            else
            {
                // find the righest node of leftSubTree
                TreeNode* pre = root->left;
                while (pre->right)
                {
                    pre = pre->right;
                }
                
                // make 'pre' node 'right' pointed to the origin rightSubTree
                pre->right = root->right;

                // make leftSubTree insert to rightSubTree
                root->right = root->left;
                root->left = nullptr;

                // consider next right node
                root = root->right;
            }
        }
    }
};

后序遍历

二叉树展开成为链表的结果就是 先序遍历 的结果。

但是按 先序遍历 结果来处理的话，更新当前结点的右指针的时候，当前结点的右指针就没有保存下来了。

    1
   / \
  2   5
 / \   \
3   4   6
   
// preOrder 
1 -> 2 -> 3 -> 4 -> 5 -> 6

所以思考 反过来，通过后序遍历 来处理。

1 2	// postOrder 6 <- 5 <- 4 <- 3 <- 2 <- 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 {
private:
    TreeNode* pre = nullptr;

public:
    void flatten(TreeNode* root) {
        if (!root)  return;

        flatten(root->right);
        flatten(root->left);

        root->right = pre;
        root->left = nullptr;
        pre = root;
    }
};

非递归先序遍历

利用栈保存上一个节点的右指针，并将其更新为当前节点。

/**
 * 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 flatten(TreeNode* root) {
        if (!root)  return;

        stack<TreeNode*> s;
        s.push(root);
        TreeNode* pre = nullptr;

        while (!s.empty())
        {
            auto tmp = s.top(); s.pop();

            // binary tree expend to linked list
            if (pre)
            {
                pre->right = tmp;
                pre->left = nullptr;
            }

            if (tmp->right) s.push(tmp->right);
            if (tmp->left)  s.push(tmp->left);
			
            // update 'pre' node to 'tmp'
            pre = tmp;
        }
    }
};

Reference

https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--26/

leetcode题解-172-阶乘后的零

发表于 2019-12-30 | 分类于数学，数论

题目

求\(N!\)在尾部有多少个0，即求有多少个2和5.
由于实际上在\(N!\)中，2的个数多于5，所以求5的个数即可，所以结果是\(N/5\)吗？
并不是，因为每过\(5^i\)个数之后，都会多出现一个5.

\(result = N/5 + N/(5^2) + N/(5^3) + ... =((N/5)/5)/5...\)

class Solution {
public:
    int trailingZeroes(int n) {
        int count = 0;
        while (n)
        {
            count += n/5;
            n /= 5;
        }

        return count;
    }
};

Reference

https://leetcode-cn.com/problems/factorial-trailing-zeroes/solution/xiang-xi-tong-su-de-si-lu-fen-xi-by-windliang-3/

https://leetcode-cn.com/problems/factorial-trailing-zeroes/solution/q172-factorial-trailing-zeroes-by-ronhou/

leetcode题解-1305-两棵二叉搜索树中的所有元素

发表于 2019-12-30

题目

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:
    vector<int> v1, v2;
    void dfs(TreeNode* root, vector<int>& v)
    {
        if (!root)  return;

        dfs(root->left, v);
        v.push_back(root->val);
        dfs(root->right, v);
    }

public:
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) 
    {
        dfs(root1, v1);
        dfs(root2, v2);     

        vector<int> res;

        size_t i = 0, j = 0;
        while (i < v1.size() && j < v2.size())
        {
            if (v1[i] <= v2[j])
            {
                res.push_back(v1[i++]);  
            }
            else
            {                 
                res.push_back(v2[j++]); 
            }
        }

        while (i < v1.size())
        {
            res.push_back(v1[i++]);
        }
        while (j < v2.size())
        {
            res.push_back(v2[j++]);
        }

        return res;
    }
};

leetcode题解-1302-层数最深叶子节点的和

发表于 2019-12-30

题目

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 sum = 0;
    int maxLevel = -1;
    void dfs(TreeNode* root, int level)
    {
        if (!root)  return;

        if (maxLevel < level)
        {
            maxLevel = level;
            sum = root->val;
        }
        else if (maxLevel == level)
        {
            sum += root->val;
        }

        dfs(root->left, level+1);
        dfs(root->right, level+1);
    }

public:
    int deepestLeavesSum(TreeNode* root) 
    {
        dfs(root, 0);

        return sum;    
    }
};

sum, maxLevel也可以改成dfs函数的引用参数。

leetcode题解-1104-二叉树寻路

发表于 2019-12-27 | 更新于 2019-12-30

def pathInZigZagTree(self, label: int) -> List[int]:
    res = []
    while label != 1:
        res.append(label)
        label >>= 1
        # 这里我采用异或实现
        label = label ^(1 << (label.bit_length() - 1)) - 1
    return [1]+res[::-1]

因为以1为根节点层次编号的满二叉树可以对应到位的表示，所以用位运算的思路即可。

因为每层的顺序在变，所以每次需要对首位外的其它位取反。

举例14=1110b，

先将14右移，变为111b，然后对除第一位外所有位取反变为100b，即它的根节点4，

同理100b，右移变为10b，对除第一位外所有位取反变为11b，即它的根节点3

一直到1结束。

总结

这是一道具有数学规律的题，不是很容易地可以发现根节点和两个孩子结点的规律。
- 根节点label = (孩子结点label / 2)除最高的1位之外后的所有位按位取反

怎么在C++里面统计一个数以二进制时，最后一位到最高的"1"位的位数。

1
2
3

// 循环统计位数
unsigned bits, var = (x < 0) ? -x : x;
for (bits = 0; var != 0; ++bits) var >>= 1;

1
2
3

// 2^n > label >= 2^(n-1) - 1
// n是label结点的层数
int numberOfBits = floor(log2(label)) + 1;

Reference

https://stackoverflow.com/questions/25754082/how-to-take-twos-complement-of-a-byte-in-c

https://stackoverflow.com/questions/29388711/c-how-to-get-length-of-bits-of-a-variable

std::floor向下取整

Bowen Peng

something about myself and my career development.