Invert binary tree – iterative method

This problem is famous due to the wellknown twett, by Max Howell.

I can not say it is hard or easy. Here just provide the iterative method as recursive method is really too easy.

In general,  you just need to swap its left and right for each node. It is natural to think it as a pre-order problem.

Source code as this:

/**
 * 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) {
     //trying to use the pre-order to solve this problem
        stack<TreeNode* > s;
        TreeNode* p = root;
        if(p != nullptr) s.push(p);
 
        while(!s.empty()){
            p = s.top();
            s.pop();
 
            if(p->right != nullptr || p->left != nullptr){
                TreeNode* temp = p->right;
                p->right = p->left;
                p->left = temp;
            }
 
            if(p->right != nullptr) s.push(p->right);
            if(p->left != nullptr) s.push(p->left);
        }
        return root;
    }
};
Posted in Algorithms, Tech | Leave a comment

Iterative Method to check if the Binary Search Tree is valid

Problem Description:

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Problem Analysis:

A valid BST always follows the left < root < right. The recursive way is check this rule is not broken. Think further to use iterative method, actually it is easy to find that this rule can be mapped to inorder traversal. Thus, the iterative method of in-order traversal of binary tree can be used to replace the recursive way. Here we just use the stack based algorithm. Time complexity is O(n). Morris Traversal is not used here.

However, there is a notice placed into the code. We set the pre_val initialized as INT_MIN. How about if the first value popped from the stack is exactly INT_MIN? In this case, the curr_val used to compare the pre_val  will lead to a incorrect conclusion that the BST is invalid. To avoid this corner case, we add a flag first_compare and initialized as 1 indicating it is still in the first compare. Thus during the first compare, if curr_val with vale of INT_MIN will not lead to return false. Once the first compare is finished, first_compare is set to 0.

Code is here and is accepted in leetcode.

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

        stack<TreeNode*> S;
        TreeNode* current = root;
        int curr_val, pre_val = INT_MIN;
        int first_compare = 1; //in first compare.

        while(!S.empty() || current){
            if(current){
                S.push(current);
                current = current->left;
            }
            else{
                current = S.top();
                curr_val = current->val;
                if(curr_val <= pre_val && first_compare == 0){
                    return false;
                }
                first_compare = 0; //after first compare
                pre_val = curr_val;
                S.pop();
                current = current->right;
            }
        }
     return true;
     }
};
Posted in Algorithms | Leave a comment

Core algorithm in real projects

http://cstheory.stackexchange.com/questions/19759/core-algorithms-deployed/19773#19773

Posted in Algorithms | Leave a comment

Matlab code to generate 1023 PN sequence.

I am using this code to generate a PN sequence with 1023 length.

h = commsrc.pn(‘GenPoly’, [[10 7 0]], ‘Mask’, [0 0 0 0 0 0 0 0 0 1]);
set(h, ‘NumBitsOut’, 1023);
pn = generate(h);
len = length(pn);
for i=1:len
if(pn(i) == 0)
pn(i) = -1;
end
end
peak = xcorr(pn);
plot(peak,’DisplayName’,’peak’,’YDataSource’,’peak’);figure(gcf);

Posted in Draft | Leave a comment

Set remote display on Ubuntu

On Server:

1. go to /etc/lighdm, in lightdm.conf add

[SeatDefaults]
xserver-allow-tcp=true

2. on terminal: xhost +

On Client:

1. export DISPLAY=$IP_ADDR_SERVER:0.0

Posted in Draft | Leave a comment

Upgrade Ubuntu to new release

sudo vi /etc/update-manager/release-upgradesto set the prompt=normal or lts.

then sudo do-release-upgrade, sometime you need -d

Posted in Draft | Leave a comment

Compressive Sensing Resources

https://www.cgran.org/wiki/CompSens 

http://dsp.rice.edu/cs

Posted in Draft | Leave a comment