https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/description/

1. To verify the result, we create a tree constructor procedure firstly.

#include <iostream>
#include <queue>
using namespace std;

typedef struct TreeNode TreeNode;

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
/**
 * 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 findSecondMinimumValue(TreeNode* root) {
    if (!root || !(root->left)) {
      return -1;
    }

    int min = root->val;
    int lresult, rresult;
    if (root->left->val != min) {
      lresult = root->left->val;
    } else {
      lresult = findSecondMinimumValue(root->left);
    }

    if (root->right->val != min) {
      rresult = root->right->val;
    } else {
      rresult = findSecondMinimumValue(root->right);
    }  
     
    if (rresult != -1 || lresult != -1) {
      return rresult > lresult ? rresult : lresult;
    }
 
    return -1;
  }
};

void inOrder(TreeNode* root)
{
  if (!root)
    return;

  if (root->left)
    inOrder(root->left);
  cout << root->val << "\n";
  if (root->right)
    inOrder(root->right);
}

void preOrder(TreeNode* root)
{
  if (!root)
    return;

  cout << root->val;
  cout << "\n";
  if (root->left)
    preOrder(root->left);
  if (root->right)
    preOrder(root->right);
}

void postOrder(TreeNode* root)
{
  if (!root)
    return;

  if (root->left)
    postOrder(root->left);
  if (root->right)
    postOrder(root->right);
  cout << root->val;
  cout << "\n";
}

int main()
{
  int input[] = {2,2,5,-1,-1,5,7};
  int size = sizeof(input) / sizeof(int);
  cout << "size = " << size << "\n";

  TreeNode **Tree = new TreeNode*[size];

  for (int i = size - 1; i >= 0; i--) {
    if (input[i] != -1) {
      Tree[i] = new TreeNode(input[i]);
      int lChild = 2 * i + 1;
      int rChild = 2 * i + 2;
      Tree[i]->val = input[i];
      if (lChild < size && (input[lChild] != -1)) {
        Tree[i]->left  = Tree[lChild];
        Tree[i]->right = Tree[rChild];
      }
    }
  }
  preOrder(Tree[0]);
  cout << "end\n\n";
 
  inOrder(Tree[0]);
  cout << "end\n\n";

  postOrder(Tree[0]);
  cout << "end\n\n";

  return 1;
}


2. resolve the problem by recursive algorithm.


 #include <iostream>
#include <queue>
using namespace std;

 typedef struct TreeNode TreeNode;

 struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
/**
 * 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 findSecondMinimumValue(TreeNode* root) {
    if (!root || !(root->left)) {
      return -1;
    }

     int min = root->val;
    int lresult, rresult;
    if (root->left->val != min) {
      lresult = root->left->val;
    } else {
      lresult = findSecondMinimumValue(root->left);
    }

     if (root->right->val != min) {
      rresult = root->right->val;
    } else {
      rresult = findSecondMinimumValue(root->right);
    }    
    
    if (rresult == -1)
      return lresult;
    else {
      if (lresult == -1)
        return rresult;
      return rresult > lresult ? lresult : rresult;
    }
  }
};

 void inOrder(TreeNode* root)
{
  if (!root)
    return;

   if (root->left)
    inOrder(root->left);
  cout << root->val << "\n";
  if (root->right)
    inOrder(root->right);  
}

 void preOrder(TreeNode* root)
{
  if (!root)
    return;

   cout << root->val;
  cout << "\n";
  if (root->left)
    preOrder(root->left);
  if (root->right)
    preOrder(root->right);
}

 void postOrder(TreeNode* root)
{
  if (!root)
    return;

   if (root->left)
    postOrder(root->left);
  if (root->right)
    postOrder(root->right);
  cout << root->val;
  cout << "\n";
}

 int main()
{
  //int input[] = {2,2,5,-1,-1,5,7};
  int input[] = {2,2,2,6,5,4,3};
  int size = sizeof(input) / sizeof(int);
  cout << "size = " << size << "\n";
  
  TreeNode **Tree = new TreeNode*[size];
  
  for (int i = size - 1; i >= 0; i--) {
    if (input[i] != -1) {
      Tree[i] = new TreeNode(input[i]);
      int lChild = 2 * i + 1;
      int rChild = 2 * i + 2;
      Tree[i]->val = input[i];
      if (lChild < size && (input[lChild] != -1)) {
        Tree[i]->left  = Tree[lChild];
        Tree[i]->right = Tree[rChild];
      }
    }
  }
  preOrder(Tree[0]);
  cout << "end\n\n";
    
  inOrder(Tree[0]);
  cout << "end\n\n";

   postOrder(Tree[0]);
  cout << "end\n\n";
  
  Solution solution;
  int result = solution.findSecondMinimumValue(Tree[0]);
  cout << result << "\n\n";
  return 1;
}

留言

張貼留言

這個網誌中的熱門文章

https://leetcode.com/contest/leetcode-weekly-contest-52/problems/longest-univalue-path/

[Implementation idea]: It is the same as longest path of a tree but with limitation. http://www.geeksforgeeks.org/diameter-of-a-binary-tree/ For Diameter of a Binary Tree, we need to recursively find out the height H() of sub-tree rooted at left & right child for each node. Then the answer is the node with max(H(node->left) + H(node->right)) + 1. For this case, an additional limit is the definition  height H'().  It needs to be the same value to it's left or right child now.   If not so, H'(node) is 0. Recursively calculate H'() for each node within the target tree. The answer is max(H'(node->left) + H'(node->right)) + 1 . #include <iostream> #include <set> #include <vector> #include <unordered_map> #include <limits.h> using namespace std; /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(i...
閱讀完整內容

https://leetcode.com/contest/leetcode-weekly-contest-52/problems/maximum-sum-of-3-non-overlapping-subarrays/

圖片
[Implementation idea]: [Native way] A native way is to check all triple candidates, filter out illegals and find the one the maximum sum. Complexity is O(n^3). [Better way] Apply dynamic programming. Complexity is O(nlogn) Complexity is O(n) Input: [1,2,1,2,6,7,5,1], 2 Output: [0, 3, 5] Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5]. We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger. Assume A(i, j) represents the maximum j Non-Overlapping Sub-arrays sum whose last  chosen index is at position i. A(i, 1) = 1. sum(A(k)) k = i, i-1, ... i-k+1, if i  >= (k - 1). 2. 0, otherwise. A(i, 2) = 1. A(i, 1) + max(A(i-k, 1)); if i  >= (2*k - 1).  2. 0, otherwise. A(i, 3) = 1. A(i, 1) + max(A(i-k, 2)); if i  >= (3*k - 1).  2. 0, otherwise. Formula A(i,1) is intuitive; Formula A(i,2) comes from the fact that - we must ended ...
閱讀完整內容