从零开始Leetcode – Day 9

##Binary Tree Zigzag Level Order Traversal

这题和Binary Tree Level Order Traversal 很想。 要注意count是从第二层开始算。
Binary Tree Zigzag Level Order Traversal
广度优先的WIKI
https://en.wikipedia.org/wiki/Breadth-first_search
明早再练习这两题。

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

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
      var res = [];
        if(!root){
            return res;
        }
        var queue = [];
        queue.push(root);

        var curNum = 0;
        var lastNum = 1;
        var list = [];
        var count = 0;
        while(queue.length){
        
            var cur = queue.shift();
            lastNum --;
            list.push(cur.val);
            if(cur.left !== null){ 
                queue.push(cur.left);
                curNum++;
            }
            if(cur.right !== null){
                queue.push(cur.right);
                curNum ++;
            }
            if(lastNum === 0){
                lastNum = curNum;
                curNum = 0;
                count = count +1;
                if(count%2 === 0){
                    list.reverse();
                }
                res.push(list);
                list = [];
            }
        }
        return res;
};

从零开始Leetcode – Day 8

Sum Root to Leaf Numbers

https://leetcode.com/problems/sum-root-to-leaf-numbers/
用private function 做， 这样子sum就在function里了。 leetcode OJ 不能全局变量。

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

var sumNumbers = function(root) {
    var sum = 0;
    var path = 0;
    helper(root, path);
    return sum;
    
    function helper(root, path){
      if(!root){
          return;
      }
      
      path = path * 10 + root.val;
      if(!root.left && !root.right){
          sum += path;
          return sum;
      }
      if(root.left){
         helper(root.left, path); 
      }
      if(root.right){
          helper(root.right, path);
      }
    }
};

从零开始Leetcode – Day 7

Sum Root to Leaf Numbers

https://leetcode.com/problems/sum-root-to-leaf-numbers/

把sum变成了array(object), 然后再pass by reference. primitive type 是pass by value.

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

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function(root) {
    var sum = {sum:0};
    var path = 0;
    helper(root, sum, path);
    return sum.sum;
    
};

var helper = function(root, sum, path){
    if(!root){
        return;
    }
    path = path * 10 + root.val;
    if(!root.left && !root.right){
        sum.sum += path;
        return sum;
        
    }
    if(root.left){
       helper(root.left, sum, path); 
    }
    if(root.right){
        helper(root.right, sum, path);
    }
};

进入medium 的tree了， 这个有bug， 明天继续

从零开始Leetcode – Day 6

Path Sum II

https://leetcode.com/problems/path-sum-ii/
要记得每次递归过后，要把上一次的pop()出来。

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

/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number[][]}
 */
var pathSum = function(root, sum) {
    var res = [];
    if(root === null){
        return res;
    }
    var list = [];
    list.push(root.val);
    helper(root, sum- root.val, list, res);
    return res;
    
};

var helper = function(root, sum, list, res){
    if(root === null){
        return ;
    }
    if(root.left === null && root.right === null && sum === 0){
        res.push(list.slice());
        return;
    }
    if(root.left !== null){
        list.push(root.left.val);
        helper(root.left, sum - root.left.val, list, res);
        list.pop();
    }
    if(root.right !== null){
        list.push(root.right.val);
        helper(root.right, sum - root.right.val, list, res);
        list.pop();
    }
}

从零开始Leetcode – Day 5

5，6，7被吞掉了。
不会广度优先搜索， Binary Tree Level Order Traversal 这题不会做。
https://leetcode.com/problems/binary-tree-level-order-traversal/
明天加油。

Binary Tree Level Order Traversal

https://leetcode.com/problems/binary-tree-level-order-traversal/

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

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
           var res = [];
        if(!root){
            return res;
        }
        var queue = [];
        queue.push(root);

        var curNum = 0;
        var lastNum = 1;
        var list = [];
        while(queue.length){
        
            var cur = queue.shift();
            lastNum --;
            list.push(cur.val);
            if(cur.left !== null){
                queue.push(cur.left);
                curNum++;
            }
            if(cur.right !== null){
                queue.push(cur.right);
                curNum ++;
            }
            if(lastNum === 0){
                lastNum = curNum;
                curNum = 0;
                res.push(list);
                list = [];
            }
        }        
        return res;
};

从零开始Leetcode – Day 4

LeetCode总结 – 树的性质篇
http://blog.csdn.net/linhuanmars/article/details/39024195
这个博客分析得不错。

总结一下今天：

1. 前一天晚上要休息好， 才有可能下班后再刷题.
2. 效率要提高。 不要花太多时间去摸索， 想不出来直接网上看代码， 转换成javascript.

Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.
https://leetcode.com/problems/binary-tree-paths/

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

var binaryTreePaths = function(root) {
    if (!root) {
        return [];
    }
    var str = "";
    var results = [];

    helper(str, results, root);
    return results;
};

var helper = function(str, results, node) {
    if (!node) {
        return;
    }

    if (node.left) {
        var leftStr = str + node.val + "->";
        helper(leftStr, results, node.left);
    }

    if (node.right) {
        var rightStr = str + node.val + "->";
        helper(rightStr, results, node.right);
    }

    if (!node.left && !node.right) {
        var path = str + node.val;
        results.push(path);
    }
};

从零开始Leetcode – Day 2

Binary Tree Paths

这题卡了半天。 这个[“1->2->5”, “1->3”] 到底要怎么实现。 今天挂了。

◢▆▅▄▃崩╰(〒皿〒)╯潰▃▄▅▇◣ 明天还要早起， GG。

https://leetcode.com/problems/binary-tree-paths/

从零开始Leetcode – Day 2

Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

1
2
3
4
5
6
7
8
9
10
11

var lowestCommonAncestor = function(root, p, q) {

    if(root.val < p.val && root.val < q.val){
        return lowestCommonAncestor(root.right , p ,q);
    }
    else if(root.val > p.val && root.val > q.val) {
        return lowestCommonAncestor(root.left , p ,q);
    }else{
        return root;
    }
};

Invert Binary Tree

1
2
3
4
5
6
7
8
9
10
11

var invertTree = function(root) {

    if(root === null){
        return null;
    }
    var tempLeft = root.left;
    var tempRight = root.right;
    root.left = invertTree(tempRight);
    root.right = invertTree(tempLeft);
    return root;
};

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

1
2
3
4
5
6
7
8
9
10
11
12
13

var minDepth = function(root) {

    if(root === null){
        return 0;
    }
    if(root.left === null){
        return minDepth(root.right) + 1;
    }
    if(root.right === null){
        return minDepth(root.left) + 1;
    }
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
};

Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

1
2
3
4
5
6
7
8
9

var hasPathSum = function(root, sum) {
    if( root === null){
        return false;
    }
    if(root.left === null && root.right === null && root.val == sum){
        return true;
    }
    return hasPathSum(root.left , sum - root.val) || hasPathSum(root.right, sum - root.val);
};

从零开始Leetcode – Day 1

Symmetric Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

var isSymmetric = function(root) {
	if(root === null){
		return true;
	}else{
		return helper(root.left , root.right);
	}
};


function helper(p , q){
	if( p === null && q ===null){
         return true;
    }     
    if( p === null || q ===null){
    	return false;
    }
    if( p.val != q.val){
    	return false;
    }else{
    	return helper(p.left, q.right) && helper(p.right , q.left);
    }
}

Same Tree

1
2
3
4
5
6
7
8
9
10
11
12

var isSameTree = function(p, q) {
    if( p === null && q === null){
        return true;
    }
    if( p !== null || q !== null ){
        return false;
    }
    if( p.val != q.val){
        return false;
    }
    return isSameTree( p.left , q.left) && isSameTree( p.right, q.right);
};

Maximum Depth of Binary Tree

1
2
3
4
5
6
7

var maxDepth = function(root) {
    if(root === null){
        return 0;
    }
    return Math.max(maxDepth(root.left) , maxDepth(root.right)) + 1;
};

Balanced Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

var isBalanced = function(root) {
    if (root === null) {
        return true;
    }
    var leftDepth = maxDepth(root.left);
    var rightDepth = maxDepth(root.right);

    if (Math.abs(leftDepth - rightDepth) <= 1) {
        return isBalanced(root.left) && isBalanced(root.right);
    } else {
        return false;
    }
};

var maxDepth = function (root) {
    if (root === null) {
        return 0;
    }
    return Math.max(maxDepth(root.left) ,maxDepth(root.right)) + 1;
};

##Binary Tree Level Order Traversal II

https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

class Solution:

# @param root, a tree node
# @return a list of lists of integers
def levelOrderBottom(self, root):
    if not root:
        return[]
    result = []
    self.helper(root, 0, result)
    result.reverse()
    return result

def helper(self, root, level, result):
    if not root:
        return
    if level+1 > len(result):
        result.append([])
    result[level].append(root.val)
    self.helper(root.left, level+1, result)
    self.helper(root.right, level+1, result)