190. Reverse Bits

Reverse bits of a given 32 bits unsigned integer.
For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

看題目大概就知道要做什麼了

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t x;
        for(auto i = 31; n; ) {
            x |= (n & 1) << i;
            n >>= 1;
            -- i;
        }
        return x;
    }
};

110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

檢查這個一顆二元樹是不是高度平衡(這邊的定義為左右兩邊的子樹高度不可以相差大於1)

解法

看code就清楚了

/**
 * 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 isBalanced(TreeNode* root) 
        {  
            return maxDepth(root) != -1;
        }  
          
        int maxDepth(TreeNode* node)
        {  
            if(!node) 
            {
                return 0;
            }
            
            auto ldepth = maxDepth(node->left);
            auto rdepth = maxDepth(node->right);
            
            if(ldepth == -1 || rdepth == -1 || abs(ldepth - rdepth) > 1)
            {
                return -1;
            }
            
            return max(ldepth, rdepth) + 1;  
        }  
    };  

113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
] 

簡單來說，就是要你找出所有符合條件的路徑。 

解法也沒有很難，跟78. Subsets的邏輯是差不多的

/**
 * 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>> pathSum(TreeNode* root, int sum) {
        
        vector<vector<int>> answer;
        vector<int> output;
        
        if (root == nullptr)
        {
            return answer;   
        }
        
        PathSumDFS(root, sum, answer, output);         
        return answer; 
                     
    }
    
    void PathSumDFS(TreeNode* node, int sum, vector<vector<int>> &answer, vector<int> &output)
    {         
        if (node == nullptr)
        {
            return;
        }
        
        output.push_back(node->val);
        
        if (node->left == nullptr && node->right == nullptr)
        {
            if(node->val == sum)
            {
                answer.push_back(output);
            }
        }
        
        PathSumDFS(node->left, sum - node->val, answer, output); 
        PathSumDFS(node->right, sum - node->val, answer, output);
        //返回上一層時需要把這個element清除
        output.pop_back();
        
    }    
};

108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

把一個排序過的array轉成一個高度平衡二元搜尋樹中。

coding的邏輯

由於是sorted過的array 所以只要將最中間的元素當成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:
    
    TreeNode* ArrayToBST(vector<int>& nums, int begin, int end)
    {
        if (begin > end)
        {
            return nullptr;
        }
        
        int mid = (end + begin)/2;
        TreeNode* root = new TreeNode(nums[mid]);
        
        root->left = ArrayToBST(nums, begin, mid - 1);
        root->right = ArrayToBST(nums, mid + 1, end);

        return root;
    }
    
    TreeNode* sortedArrayToBST(vector<int>& nums)
    {
        return ArrayToBST(nums, 0, nums.size() - 1);
    }
};

104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

我想不用多說了吧
code也很簡單...

   class Solution {  
    public:  
        int maxDepth(TreeNode *root) {  
 
            if(root == NULL)
            {
                return 0;
            }
            
            return 1 + max( maxDepth(root->left), maxDepth(root->right) );  
        }  
    };  

搞定

101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3 

簡單來說，判斷是否為對稱樹

程式碼 

class Solution {
public:
    bool isSymmetric(TreeNode* root) 
    {
        
        if (root == NULL) return true;
        
        return isSymc(root->left, root->right);
        
    }
    
    bool isSymc(TreeNode* left, TreeNode* right)
    {
        if (left == nullptr)
        {
            return right == nullptr;
        }
        
        if (right == nullptr)
        {
            return left == nullptr;
        }
        
        if (left->val != right->val)
        {
            return false;
        }
        
        // 檢查是否對稱
        if (!isSymc(left->right, right->left))
        {
            return false;
        }
        
        if (!isSymc(left->left, right->right))
        {
            return false;
        }
            
        return true;
    }
    
};

226. Invert Binary Tree

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

不用多說了，就是反轉二元樹

方法有好幾種。我這邊用最快的方法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:
  
  TreeNode* invertTree(TreeNode* root) {

    if(nullptr == root) return root;

    stack<TreeNode*> myQueue;   // our queue to do BFS
    myQueue.push(root);         // push very first item - root

    while(!myQueue.empty()){    // run until there are nodes in the queue 
        TreeNode *node = myQueue.top();  // get element from queue
        myQueue.pop();                     // remove element from queue

        if(node->left != nullptr){         // add left kid to the queue if it exists
            myQueue.push(node->left);
        }
        if(node->right != nullptr){        // add right kid 
            myQueue.push(node->right);
        }

        // invert left and right pointers      
        swap(node->left, node->right);

    }
    return root;
}       
};