Binary Tree Inorder traversal -- Leetcode

Question:

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

Answer:

* Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> res;
        if(!root)return res;
        
        stack<TreeNode*> stk;
        TreeNode *cur = root;
             
        while(!stk.empty() || cur){
            if(cur){              
                stk.push(cur);
                cur= cur->left;     //If left child != NULL, will push continuously left child into stack.
            }
            else{
                cur= stk.top();
                stk.pop();
                res.push_back(cur->val);
                cur= cur->right;
            }
        }
        return res;
    }

};

Pow(x,n) -- Leetcode

Question:

Implement pow(x, n).

题意计算x的n次方，考虑复杂度和n的取值。

n有可能是正数或者负数，分开计算。

用递归的做法讲复杂度降到O（logn）。

[cpp] view plaincopy

1. class Solution {  
2. public:  
3.     double pow(double x, int n) {  
4.         if(n==0)return 1;  
5.         if(n==1)return x;  
6.         double temp=pow(x,abs(n/2));  
7.         if(n>0)  
8.         {  
9.             if(n&1)return temp*temp*x;  
10.             else return temp*temp;  
11.         }  
12.         else   
13.         {  
14.             if(n&1)return 1.0/(temp*temp*x);  
15.             else return 1.0/(temp*temp);  
16.         }  
17.     }  
18. };   

Converted Sorted List to Binary Search Tree -- Leetcode

这个题是二分查找树的题目，要把一个有序链表转换成一棵二分查找树。其实原理还是跟Convert Sorted Array to Binary Search Tree这道题相似，我们需要取中点作为当前函数的根。这里的问题是对于一个链表我们是不能常量时间访问它的中间元素的。这时候就要利用到树的中序遍历了，按照递归中序遍历的顺序对链表结点一个个进行访问，而我们要构造的二分查找树正是按照链表的顺序来的。思路就是先对左子树进行递归，然后将当前结点作为根，迭代到下一个链表结点，最后在递归求出右子树即可。整体过程就是一次中序遍历，时间复杂度是O(n)，空间复杂度是栈空间O(logn)加上结果的空间O(n)，额外空间是O(logn)，总体是O(n)。代码如下： 

[java] view plaincopy

1. public TreeNode sortedListToBST(ListNode head) {  
2.     if(head == null)  
3.         return null;  
4.     ListNode cur = head;  
5.     int count = 0;  
6.     while(cur!=null)  
7.     {  
8.         cur = cur.next;  
9.         count++;  
10.     }  
11.     ArrayList<ListNode> list = new ArrayList<ListNode>();  
12.     list.add(head);  
13.     return helper(list,0,count-1);  
14. }  
15. private TreeNode helper(ArrayList<ListNode> list, int l, int r)  
16. {  
17.     if(l>r)  
18.         return null;  
19.     int m = (l+r)/2;  
20.     TreeNode left = helper(list,l,m-1);  
21.     TreeNode root = new TreeNode(list.get(0).val);  
22.     root.left = left;  
23.     list.set(0,list.get(0).next);  
24.     root.right = helper(list,m+1,r);  
25.     return root;  
26. }  

Spiral Matrix -- Leetcode

1. class Solution {  
2. //key observe: when any component is done, its beginX,endX or beginY,endX will change  
3. public:  
4.     vector<int> spiralOrder(vector<vector<int> >& matrix) {  
5.         vector<int> result;  
6.         if (matrix.empty()) return result;  
7.         int beginX = 0, endX = matrix[0].size() - 1;  
8.         int beginY = 0, endY = matrix.size() - 1;  
9.         while (true) {  
10.             // From left to right  
11.             for (int i = beginX; i <= endX; ++i)  
12.                 result.push_back(matrix[beginY][i]);  
13.             if (++beginY > endY) break;  
14.             // From top down  
15.             for (int i = beginY; i <= endY; ++i)  
16.                 result.push_back(matrix[i][endX]);  
17.             if (beginX > --endX) break;  
18.             // From right to left  
19.             for (int i = endX; i >= beginX; --i)  
20.                 result.push_back(matrix[endY][i]);  
21.             if (beginY > --endY) break;  
22.             // From bottom up  
23.             for (int i = endY; i >= beginY; --i)  
24.                 result.push_back(matrix[i][beginX]);  
25.             if (++beginX > endX) break;  
26.         }  
27.         return result;  
28.     }  
29. };  

Evaluate Reverse Polish Notation -- Leetcode

Question:

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Answer:
[C++]

1. class Solution {  
2. public:  
3.     int evalRPN(vector<string> &tokens) {  
4.         stack<int> numeric;  
5.           
6.         for(auto& t : tokens)  
7.         {  
8.             if (isdigit(t[0]) || t.size()>1)  
9.                 numeric.push(atoi(t.c_str()));  
10.             else  
11.             {  
12.                 int o1, o2;  
13.                 o2 = numeric.top();  
14.                 numeric.pop();  
15.                 o1 = numeric.top();  
16.                 numeric.pop();  
17.                   
18.                 switch(t[0])  
19.                 {  
20.                     case '+':  
21.                         numeric.push(o1 + o2);  
22.                         break;  
23.                     case '-':  
24.                         numeric.push(o1 - o2);  
25.                         break;  
26.                     case '*':  
27.                         numeric.push(o1 * o2);  
28.                         break;  
29.                     case '/':  
30.                         numeric.push(o1 / o2);  
31.                         break;  
32.                 }  
33.             }  
34.         }  
35.           
36.         return numeric.top();  
37.     }  
38. };

[Python]

计算符号在后缀上。可以理解成二叉树的后序遍历（操作符都在父节点上）

[python] view plaincopy

1. class Solution:  
2.     # @param tokens, a list of string  
3.     # @return an integer  
4.     def operator(self,a,b,op):  
5.         a = int(a)  
6.         b = int(b)  
7.         if op == "+":  
8.             return int(a+b)  
9.         elif op  == "-":  
10.             return int(a-b)  
11.         elif op == "*":  
12.             return int(a*b)  
13.         elif op == "/":  
14.             if b == 0:  
15.                 return 0  
16.             else:  
17.                 return int(float(a)/float(b))  
18.           
19.           
20.     def evalRPN(self, tokens):  
21.         stack = []  
22.         tl = len(tokens)  
23.         op = ["+","-","*","/"]  
24.         for i in range(tl):  
25.             if tokens[i] in op:  
26.                 a = stack.pop()  
27.                 b = stack.pop()  
28.                 c = self.operator(b,a,tokens[i])  
29.                 stack.append(c)  
30.             else:  
31.                 stack.append(tokens[i])  
32.         return int(stack[0])