Posted on   |   In

从零开始Leetcode – Day 18

Binary Search Tree Iterator

https://leetcode.com/problems/binary-search-tree-iterator/

  1. 这里是用stack 来实习左中右， inorder 遍历。
  2. 实现stack, push和pop， LIFO 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * Definition for binary tree
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
var stack =[];
/**
 * @constructor
 * @param {TreeNode} root - root of the binary search tree
 */
var BSTIterator = function(root) {
    while(root !== null){
        stack.push(root);
        root = root.left;
    }
    
};


/**
 * @this BSTIterator
 * @returns {boolean} - whether we have a next smallest number
 */
BSTIterator.prototype.hasNext = function() {
    return (stack.length > 0) ? true : false;
    
};

/**
 * @this BSTIterator
 * @returns {number} - the next smallest number
 */
BSTIterator.prototype.next = function() {
    var node = stack.pop();
    var res = node.val;
    if(node.right !== null){
        node = node.right;
        while(node !== null){
            stack.push(node);
            node = node.left;
        }
        
    }
    return res;
    
};

/**
 * Your BSTIterator will be called like this:
 * var i = new BSTIterator(root), a = [];
 * while (i.hasNext()) a.push(i.next());
*/

Posted on   |   In

从零开始Leetcode – Day 17

Binary Tree Inorder Traversal

https://leetcode.com/problems/binary-tree-inorder-traversal/
明天写非递归。

、、、
/**

  • @param {TreeNode} root
  • @return {number[]}
    */
    var inorderTraversal = function(root) {
    var res = [];
    helper(root, res);
    return res;

};

var helper = function(root, res){
if(root === null){
return;
}
helper(root.left, res);
res.push(root.val);
helper(root.right, res);
}
、、、

Posted on   |   In

从零开始Leetcode – Day 16

Flatten Binary Tree to Linked List

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

1 注意考虑起始条件， 和终止条件。
2 晚上做不了算法题， 白天做过的，到了晚上不能debug.
3 所有题目要重做一次， 才会产生效果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
    

    var pre = [];
    pre.push(null);
    helper(root, pre);
};

var helper = function(root, pre){
    if(root ===null){
        return;
    }
    var right = new TreeNode();
    right = root.right;
    if(pre[0] !== null){
        pre[0].left = null;
        pre[0].right = root;
    }
    pre.unshift(root);
    helper(root.left, pre);
    helper(right, pre);
};

Posted on   |   In

从零开始Leetcode – Day 15

Count Complete Tree Nodes

https://leetcode.com/problems/count-complete-tree-nodes/
注意直接递归会超时， log(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
var countNodes = function(root) {
    if(root ===null){
        return 0;
    }
    var l = leftDepth(root);
    var r = rightDepth(root);
    
    if(l =r){
        return (Math.pow(2, l)-1);
    } else{
       return 1 + countNodes(root.left) + countNodes(root.right);
    }
    
};

var leftDepth = function(root){
    var h = 0;
    while(root !==null){
        h++;
        root = root.left
        
    }
    return h;
};

var rightDepth = function(root){
    var h = 0;
    while(root !==null){
        h++;
        root = root.right;
    }
    return h;
};

Posted on   |   In

从零开始Leetcode – Day 14

Convert Sorted List to Binary Search Tree

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
    if(!head){
        return null;
    }
    var cur = head;
    var count = 0;
    while(cur !== null){
        cur = cur.next;
        count++;
    }
    var list = [];
    list.push(head);
    return helper(list, 0, count-1);
};

var helper = function(list, l, r){
    if(l>r){
        return null;
    }
    var m = Math.floor((l+r)/2);
    // left 
    var left = helper(list, l, m-1);
    
    var root = new TreeNode(list[0].val);
    root.left = left;
    list[0] = list[0].next;
    
    // right
    root.right = helper(list, m+1, r);
    return root;
}

Posted on   |   In

从零开始Leetcode – Day 13

Convert Sorted Array to Binary Search Tree

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
http://blog.csdn.net/linhuanmars/article/details/23904883

前2天得太难了，跳过。以后碰到太难的直接跳过。 明天继续Angular之旅。快要看完了, 加油~~！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    if(nums === null || nums.length ===0){
        return null;
    }
    return helper(nums, 0, nums.length -1);
};

var helper = function(nums, l ,r){
     if(l > r){
            return null;
        }
        var m = Math.round((l+r)/2);
        var root = new TreeNode(nums[m]);
        root.left = helper(nums, l, m-1);
        root.right = helper(nums, m+1, r);
        return root;
}

Posted on   |   In

从零开始Leetcode – Day 12

Construct Binary Tree from Inorder and Postorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
递归时有点复杂， 明天把把11，12的一起干了。 明天开始进入angular.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var buildTree = function(inorder, postorder) {
    node_nums = inorder.length;
    post_i = node_nums - 1;
    return build_tree(0, node_nums-1);
    
    function build_tree(start, end) {
        if (start <= end) {
            var root = new TreeNode(postorder[post_i]);
            // var root_index = postToIn.get(postorder[post_i])
            var root_index = inorder.indexOf(postorder[post_i])
            post_i--;
            root.right = build_tree(root_index+1, end);
            root.left = build_tree(start, root_index-1);
            return root;
        }
        return null;
    }
};

Posted on   |   In

从零开始Leetcode – Day 11

Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
今天把 preorder, inorder, postorder. traversal 就是MLR, LMR, LRM. 递归思想， 每次看成一个3个节点的树。

http://blog.csdn.net/linhuanmars/article/details/24389549
明天早上在把它完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    
    if(!preorder || !inorder){
        return null;
    }
    var map = [];
    for(var i = 0; i < inorder.length; i++){
        map.push(inorder[i]);
    }
    return helper(preorder, 0,preorder.length -1, inorder, 0 , inorder.length -1, map);
    
    function helper(preorder, preL, preR, inorder, inL, inR, map){
        if(preL > preR || inL > inR){
            return null;
        }
        var root = new TreeNode(preorder[preL]);
        var index = map.indexOf(root.val);
        root.left = helper(preorder, preL +1, index-inL +preL, inorder, inL, index-1, map);
        root.right = helper(preorder, preL + index + inL +1, preR, inorder, index+1, inR ,map);
        return root;
    }
};

Posted on   |   In

从零开始Leetcode – Day 10

##Binary Tree Level Order Traversal
不是很熟悉 curNum, lastNum. 理解得不够透彻。早点休息， 明天再努力。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
      var queue = [];
      var list = [];
      var res = [];
      if(!root){
          return res;
      }
      queue.push(root);
      curNum = 0;
      lastNum =1;
      while(queue.length){
          var cur = queue.shift();
          list.push(cur.val);
          lastNum--;
          if(cur.left){
              curNum++;
              queue.push(cur.left);
          }
          if(cur.right){
              curNum++;
              queue.push(cur.right);
          }
          if(lastNum ===0){
              lastNum = curNum;
              curNum = 0;
              res.push(list);
              list = [];
          }
          
      }
      return res;
};

Posted on

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment