Connect nodes at the same level in a binary tree

May 16, 2016 

Connect nodes at the same level in a binary tree  

http://www.geeksforgeeks.org/connect-nodes-at-same-level/   (? bug)

better one:
http://javabypatel.blogspot.ca/2015/08/connect-nodes-at-same-level-in-binary-tree-using-constant-extra-space.html

Using Queue - 
http://javabypatel.blogspot.ca/2015/08/connect-nodes-at-same-level-in-binary-tree.html

Question and answer:

1. How long do you study the problem? What do you learn? 

Julia spent more than 1 hour to study the blogs above. She will write down her own notes about the test case, analysis and solution, and post them in the blog. Encourage herself to write, to share and to improve her confidence on problem solving. 

Will come back soon. 

code challenge: count of substring

February 28, 2016

Problem statement

Problems solved in the progression of coding:
1. Runtime error - exceed time limit
   naive solution - compare each substring if it contains 00 or 11
2. Console.ReadLine only reads up to 256 chars, the input is up to 100000 chars.
3. Recursive calls - stack overflow - string length is up to 100000
4. Using iterative solution to replace recursive solution

First, wrote a solution in 20 minutes, but Time exceeding limit - TLE error.
Solution 1: C# code


Solution 2: C# code

So, write second version using recursive to avoid redundant calculation: stack overflow problem

Solution 3: C# code

Then, wrote third version with iterative solution:

Solution 4: C# code
(HackerRank embedded C# executable - wrong answer, but Visual express is ok! Cannot figure out! )


Spent more than 4 hours on this easy question. Totally invest 3 hours nonstop on Sunday afternoon on this problem solving.

What we say to encourage this behavior - have guts to fail. This is just the practice.

March 7, 2017

Need to review last practice and find out a solution.

Morris post order traversal algorithm

Sept. 5, 2015

花时间把代码读明白, 比光看书强. 动手写代码, 改代码,  
兴趣是最好的老师. 多记几个例子, 增加情趣. 

举个例子关于中序遍历, 

           4

        /     \

       2       6

     /  \     / \

    1   3   5   7 

easy way to travel is to remember the order of its position in the horizontal way 

       

现在, 要做Morris 的后序遍历, 有一个技巧, 是在我写完这个C#代码才发现的, 

                     

9                 /    \

5      8

/ \       \

1   4     7

/ \   /

2   3 6 就是从最左边开始, 遍历五次,   1,   2,   3, 4, 5   6,   7, 8, 9,  最后结果是 1 2 3 4 5 6 7 8 9  加一个dummy node, with left child is the root node.

Morris post order traversal

blogs to read:
http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html


C# implementation:
https://github.com/jianminchen/MorrisOrder/blob/master/MorrisPostOrder.cs


Morris order in order traversal

https://github.com/jianminchen/MorrisInOrderTraverse/blob/master/Program.cs

Leetcode 226: invert a binary tree

Invert a binary tree

http://www.wengweitao.com/leetcode-invert-binary-tree.html

http://mojijs.com/2015/06/196603/index.html

Binary tree upside down 

http://bangbingsyb.blogspot.ca/2014/11/leetcode-binary-tree-upside-down.html

Github source code:

https://github.com/jianminchen/leetcode-tree/

June 15, 2015

Write C# code 

/**
         * Latest update: on June 16, 2015
         * Leetcode: 
         * Invert a binary tree
         * Reference: 
         * http://www.zhihu.com/question/31202353
         * 
         * 7 lines of code - using recursion
         */
        public static Node invertBinaryTree(Node root)
        {
            if (root == null)
                return null;

            Node temp = root.left;
            root.left = root.right;
            root.right = temp;

            invertBinaryTree(root.left);
            invertBinaryTree(root.right);

            return root; 
        }

        /**
         * Latest update: on June 16, 2015
         * Leetcode: Invert a binary tree
         * using iterative solution 
         */
        public static Node invertBinaryTreeIterative(Node root)
        {
            if (root == null)
                return null;

            Queue q = new Queue();
            q.Enqueue(root);

            /*
             * consider the queue: 
             */
            while (q.Count > 0)
            {
                Node nd = (Node)q.Dequeue();

                Node tmp = nd.left;
                nd.left = nd.right;
                nd.right = tmp;

                if (nd.left != null)
                    q.Enqueue(nd.left);
                if (nd.right != null)
                    q.Enqueue(nd.right); 
            }

            return root; 
        }