LeetCode Problem: Maximum Depth of Binary Tree

Recursively count the depth of tree node. One node’s depth is the maximum depth of it’s children’s depth + 1 or 0 if node is NULL.
递归计算就可以了,如果是空节点,深度是0,否则这个节点的子树的最大深度是其子节点最大深度 + 1。



Maximum Depth of Binary Tree Sep 30 ’12
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.



Code, 64ms pass large set

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(root == NULL) return 0;
        int leftdep = maxDepth(root->left);
        int rightdep = maxDepth(root->right);
        return 1 + std::max(leftdep,rightdep);
    }
};

LeetCode Problem: Pascal’s Triangle

The problem is simple, each element in the triangle is the sum of two numbers above it.
这个题目简单,三角形中每一个元素的值是其上面两个值的和。

So, just build the rows one by one according the row above it. And the first row is {1}.
根据当前行的上面一层数字,就可以逐行生成整个三角形了。初值是第一行:{1}



Pascal’s Triangle Oct 28 ’12
Given numRows, generate the first numRows of Pascal’s triangle.
For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]



Code, 12ms pass large test set

class Solution {
public:
    vector > generate(int numRows) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector >ret;
        if(numRows == 0) return ret;
        //first row
        ret.push_back(vector(1,1));
        //rest rows;
        for(int nr = 2; nr <= numRows; ++nr) {
            vector thisrow(nr,1);
            vector &lastrow = ret[nr-2];
            for(int ic = 1; ic < nr - 1; ++ic) {
                thisrow[ic] = lastrow[ic-1] + lastrow[ic];
            }
            ret.push_back(thisrow);
        }
        return ret;
    }
};

Algorithm Problem: Find Out the Minimum Number that Great or Equal to a Given Number In BST

Given a BST and a Number k, find out the minimum number p that p >= k.
给定一个BST的根,以及一个数k,返回在BST中的不小于k的最小的节点。

The method is descriped below, in the code.
具体方法在代码中注释得很清楚了.

The recursive and non-recursive code is included.
下面的代码中包含了递归和非递归两种.


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
};
TreeNode *findKRecursive(TreeNode *root, int k) {
    if (NULL == root) {
        //there is no node that match the requisite.
        //在这颗空子树中是找不到目标的
        return NULL;
    }
    if (root->val == k) {
        //the node equal to k is find
        //找到了正好等于k的节点,这就是全局要找的节点。
        return root;
    } else if (root->val < k) {
        //root is less than k, so the result node is in it's right sub-tree, if there is.
        //如果根节点的值小于k,那么唯一的满足条件的节点只能去右子树中查找,如果右子树中没有,那整棵树也没有。
        return findKRecursive(root->right, k);
    } else {
        //root is > k, so the target node may be in it's left sub-tree, or is the current node.
        //如果根节点的值>k,那么值更小的满足要求的节点可能出现在左子树中
        TreeNode *knode = findKRecursive(root->left, k);
        if (knode) {
            //if a node is found in left sub-tree, then knode->value must <= cur->value, so return it
            //如果左子树中确实找到了一个节点满足要求,那么他的值一定不大于当前节点的值
            return knode;
        } else {
            //or there is no node which value is >= k, then , root is the best choice for the result.
            //否则左子树中没有>=k的节点,那最小的满足>=k要求的节点就是root了。
            return root;
        }
    }
}

TreeNode *findK(TreeNode *root, int k) {
    TreeNode *lastFound = NULL;//record the last node found which value is >= k
    TreeNode *cur = root;//current node to search for.
    while (cur) {
        if (cur->val == k) {
            //the node equal to k is find
            //找到了正好等于k的节点,这就是全局要找的节点。
            return cur;
        } else if (cur->val > k) {
            //root is > k, so the result may be in it's left sub-tree, or cur is the best result
            //如果根节点的值>k,那么值更小的满足要求的节点可能出现在左子树中,如果左子树没有的话,这就是最好的选择
            lastFound = cur;
            cur = cur->left;
        } else {
            //root is less than k, so the result node is in it's right sub-tree, if there is.
            //如果根节点的值小于k,那么唯一的满足条件的节点只能去右子树中查找,如果右子树中没有,那整棵树也没有。
            cur = cur->right;
        }
    }
    return lastFound;
}

LeetCode Problem: Populating Next Right Pointers in Each Node II

The code in the previous article LeetCode Problem: Populating Next Right Pointers in Each Node, Level traversal of binary tree is also adapted to this situation.
上一题LeetCode Problem: Populating Next Right Pointers in Each Node, Level traversal of binary tree的答案对这个题目仍然是适用的。



Populating Next Right Pointers in Each Node II
Follow up for problem “Populating Next Right Pointers in Each Node”.
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
You may only use constant extra space.
For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

LeetCode Problem: Populating Next Right Pointers in Each Node, Level traversal of binary tree

It’s easy to doing this by using a queue, doing a level traversal of binary tree.
题目相对简单,用一个队列来进行广度优先遍历就可以了,用一个NULL来指示每一层的结束。



Populating Next Right Pointers in Each Node
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL



Code, 160ms pass the large test set.

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        queue q;
        if(root) {
            q.push(root);
            q.push(NULL);
        }
        while(q.size()) {
            TreeLinkNode *cur = q.front();
            q.pop();
            if(cur) {
                cur->next = q.front();
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            } else {
                if (q.size()) q.push(NULL);
            }
        }
    }
};



Code rewrite at 2013-1-19, more simple

class Solution {
public:
    void connect(TreeLinkNode *root) {
        queue q;
        q.push(root);
        q.push(NULL);
        while(true) {
            TreeLinkNode *cur = q.front();
            q.pop();
            if(cur) {
                cur->next = q.front();
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            } else {
                if (q.size() == 0 || q.front() == NULL) return;
                q.push(NULL);
            }
        }
    }
};

Algorithm Problem:Swap the left and right sub-tree in a binary tree without recursion

Just swap the tree nodes’ left and right child, in the post traversal order.
只需要在后序遍历的过程中,交换节点的左右子树即可。



Code

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void swapLeftAndRight(TreeNode *root) {
        bool forward = true;
        TreeNode *pre = NULL;
        stack trace;
        if(root) trace.push(root);
        
        while(trace.size()) {
            TreeNode *cur = trace.top();
            if(forward) {
                if(cur->left && pre != cur->left) {
                    trace.push(cur->left);
                } else {
                    forward = false;
                }
            } else {
                if(cur->right && pre != cur->right) {
                    trace.push(cur->right);
                    forward = true;
                } else {
                    //all the child has finished visit, then swap the left and right of cur
                    TreeNode *t = cur->left;
                    cur->left = cur->right;
                    cur->right = t;
                    
                    trace.pop();
                }
            }
            pre = cur;
        }
    }
};

LeetCode Problem:Flatten Binary Tree to Linked List

We can notice that in the flattened tree, each sub node is the successor node of it’s parent node in the pre-order of the original tree. So, we can do it in recursive manner, following the steps below:
1.if root is NULL return;
2.flatten the left sub tree of root, if there is left sub-tree;
3.flatten the right sub-tree of root, if has;
4.if root has no left sub-tree, then root is flattened already, just return;
5.we need to merge the left sub-tree with the right sub-tree, by concatenate the right sub-tree to the last node in left sub-tree.
5.1.find the last node in the left sub tree, as the left is flattened, this is easy.
5.2.concatenate the right sub-tree to this node’s right child.
5.3.move the left sub-tree to the right for root.
5.4.clear the left child of root.
6.done.

<br>
Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6



Code:48ms to accept with large test set.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (root == NULL) return;
        //1.flat the left subtree
        if (root->left)
            flatten(root->left);
        //2.flatten the right subtree
        if (root->right)
            flatten(root->right);
        //3.if no left return
        if (NULL == root->left)
            return;
        //4.insert left sub tree between root and root->right
        //4.1.find the last node in left
        TreeNode ** ptn = & (root->left->right);
        while (*ptn)
            ptn = & ((*ptn)->right);
        //4.2.connect right sub tree after left sub tree
        *ptn = root->right;
        //4.3.move left sub tree to the root's right sub tree
        root->right = root->left;
        root->left = NULL;
        
    }
};



Code rewrite at 2013-2-20, non-recursive version

class Solution {
public:
    void flatten(TreeNode *root) {
        bool f = true;
        stack t;
        TreeNode *pre = NULL;
        if(root) {
            t.push(root);
        }
        
        while(t.size()) {
            TreeNode *cur = t.top();
            if(f) {
                if(cur->left && cur->left != pre) {
                    t.push(cur->left);
                } else {
                    f = false;
                }
            } else {
                if(cur->right && cur->right != pre) {
                    t.push(cur->right);
                    f = true;
                } else {
                    t.pop();
                    //at this time, the sub-tree of cur is flattened, so just flatten the cur
                    TreeNode *left = cur->left;
                    if(left) {
                        TreeNode *lastLeft = left;
                        while(lastLeft->right) {
                            lastLeft = lastLeft->right;
                        }
                        lastLeft->right = cur->right;
                        cur->right = left;
                        cur->left = NULL;
                    }
                }
            }
            pre = cur;
        }
    }
};

LeetCode题目:Convert Sorted List to Binary Search Tree

问题比上一个难一点,如果是可以用O(n)空间的话,倒是可以开一个数组放上这n个数,然后按上一个问题的解法去做。总体时间O(n),空间O(n)。

不过这题这样出应该不是这个意思。假如不用O(n)空间的话:
可以先数一下一共有多少个节点。O(n)时间。
然后去找到根节点(数数),然后根节点之前是左子树,之后是右子树,并且两个子树的节点个数都是可以直接计算出来的,递归解这个问题就可以了。
那么总体时间复杂度是O(n*logn),空间O(logn)



Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.



代码:114ms过大集合

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    TreeNode *formTree(ListNode *head, int count) {
        if(count <= 0) return NULL;
        int rootIndex = count / 2;
        ListNode *rootNode = head;
        for(int ir = 0; ir < rootIndex; ++ir) {
            rootNode = rootNode->next;
        }
        TreeNode *root = new TreeNode(rootNode->val);
        root->left = formTree(head,rootIndex);
        root->right = formTree(rootNode->next, count - rootIndex - 1);
        return root;
    }
public:
    TreeNode *sortedListToBST(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        //1. find the node count, takes O(n) time
        int nodeCount = 0;
        for(ListNode *cur = head; cur != NULL; cur = cur->next) {
            ++nodeCount;
        }
        
        //2. form the tree with the middle as the root
        return formTree(head, nodeCount);
    }
};

LeetCode题目:Convert Sorted Array to Binary Search Tree

对排序的数组进行二分查找样式的遍历就行了。



Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.



代码:84ms过大集合

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    TreeNode *sortedArrayToBST(vector &num,int si, int ei) {
        if(si > ei) return NULL;
        int mid = (ei + si) / 2;
        TreeNode *root = new TreeNode(num[mid]);
        root->left = sortedArrayToBST(num,si,mid - 1);
        root->right = sortedArrayToBST(num,mid + 1,ei);
        return root;
    }
    
public:
    TreeNode *sortedArrayToBST(vector &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return sortedArrayToBST(num,0,num.size() - 1);
    }
};

LeetCode题目:Construct Binary Tree from Inorder and Postorder Traversal

这题和上一道题类似,也是首先在postorder中,最后那一个肯定是整棵树的根,然后在inorder中查找这个根,找到之后就能确定左子树和右子树的后序遍历和中序遍历,然后递归求解。



Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.



代码:120ms过大集合

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *buildTree(vector &iorder, int isi, int iei, vector &porder, int psi, int pei) {
        if(iei - isi < 0 || iei - isi != pei - psi) {
            return NULL;
        }
        //the porder[pei] is the root of this tree
        TreeNode *root = new TreeNode(porder[pei]);
        //find the root in the iorder to seperate it into left sub tree and right sub tree
        int riii = -1;//root index in inorder array
        for(int i = isi; i <= iei; ++i) {
            if(iorder[i] == root->val) {
                riii = i;
                break;
            }
        }
        if(riii == -1) return root;//error
        int lnodes = riii - isi;
        //for the left sub tree
        //the isi to riii - 1 in inorder array will be it's inorder traversal
        //and the psi to psi + lnodes - 1 in postorder array will be it's post order traversal
        root->left = buildTree(iorder, isi, riii - 1, porder, psi, psi + lnodes - 1);
        //for the right sub tree is similary to the left
        root->right = buildTree(iorder, riii + 1, iei, porder, psi + lnodes, pei - 1);
        return root;
    }
    TreeNode *buildTree(vector &inorder, vector &postorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return buildTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() -1);
    }
};

LeetCode题目:Construct Binary Tree from Preorder and Inorder Traversal

这曾经是一道很难的题目,看来这一阵的锻炼确实是有效果的。


方法是,画一棵树出来,比如:

   1
 /   \
2     3
 \    /
  4  5

这棵树好用,在于其中包含了所有的可能性,(2度,1度(左右),0度节点都有)。
它的preorder是:1,2,4,3,5
他的inorder是:2,4,1,5,3


那么递归的看这个问题,首先preorder的第一个必然是根(1),然后此节点在inorder中的下标是2,那么在inorder中,处于1之前的两个节点2,4是左子树的;反之5,3是右子树的。
针对左子树,2,4就是它的inorder,而在preorder中,除开第一个根,数两个节点的子序列正好是2,4,这是左子树的preorder。这样这个问题就自然变成递归了:
即,其左子树的preorder是(2,4),inorder是(2,4);类似有右子树preorder(3,5),inorder(5,3)。
然后边界情况是某数的preorder和inorder遍历的长度都是1,比如{x},那么这棵树就是以x为值的节点。
这样就可以写出代码了。



Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.



代码:124ms过大集合

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
typedef TreeNode TN;
class Solution {
    TN *buildTree(vector &preorder,int psi,int pei,
                  vector &inorder, int isi, int iei) {
        if(pei - psi < 0 || pei - psi != iei - isi) 
            return NULL;
        //root of sub tree
        TN *root = new TN(preorder[psi]);
        //find this value in inorder to locate the root in inorder
        int riii = -1;//root index in inorder
        for(int itemp = isi; itemp <= iei; ++ itemp) {
            if(inorder[itemp] == root->val) {
                riii = itemp;
                break;
            }
        }
        if(riii != -1) {
            //calculate the nodes count in left tree
            int leftCount = riii - isi;
            TN *left = buildTree(preorder,psi + 1, psi + leftCount, inorder, isi, riii - 1);
            root->left = left;
            TN *right = buildTree(preorder,psi + leftCount + 1,pei, inorder, riii + 1, iei);
            root->right = right;
        }
        return root;
    }
public:
    TreeNode *buildTree(vector &preorder, vector &inorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        TN *root = buildTree(preorder,0,preorder.size() - 1,inorder,0,inorder.size() - 1);
    }
};

LeetCode题目:Binary Tree Zigzag Level Order Traversal

比较简单,广度优先变一下就可以了,用一个bool记录是从左到右还是从右到左,每一层结束就翻转一下。



Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]



代码:28ms过大集合

/**
 * 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 > zigzagLevelOrder(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector > ret;
        if(NULL == root) return ret;
        
        queue que;
        que.push(root);
        que.push(NULL);//level end point
        
        bool l2r = true;//left to right
        
        vector level;
        while(true) {
            TreeNode *cur = que.front();
            que.pop();
            if(cur) {
                level.push_back(cur->val);
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            } else {
                if(l2r) {
                    ret.push_back(level);
                } else {
                    vector temp;
                    for(int i = level.size() - 1 ; i >= 0; --i) {
                        temp.push_back(level[i]);
                    }
                    ret.push_back(temp);
                }
                level.erase(level.begin(),level.end());
                l2r = !l2r;
                
                if(que.size() == 0) break;
                que.push(NULL);
            }
        }
        
        return ret;
    }
};

LeetCode题目:Binary Tree Maximum Path Sum

这道题好难,因为在一颗二叉树中有多种情况,这条最长的路径有可能是从某个中间节点直接到某个叶子节点的,也有可能是两条上述路径连接在一个中间节点上(这个中间节点可能是root也可能不是),也有可能只是一个单独的节点。

情况太多导致问题很复杂,不好分析,这题花了我至少两个小时去解决。

一开始从自上而下的方法去想,想到了可以计算出每一个节点到root的最大值,然后最后拼一下最大值,得到整体最大。但是这里假设了路径都是过root的。显然不对。

然后想level优先遍历的话,如果知道了上面的情况,下面一层可解么?陷入死胡同至少30min,gg。

然后想自下而上,如果知道了左右子树的情况,自身的情况能得到么?很快就有了肯定回答。
但是这个solution也相对复杂,针对每个节点需要知道的是:
1.终止在这个节点上(往自己子树走)的最大路径值是多少
2.经过这个节点的最大值是多少?(从左子树走过自己到右子树)
3.不经过此节点的子树中可能获得的最大值是多少?

在知道这三个量之后,问题变得明确可解了。那就是递归,先计算出左右子树的这三个值,然后:
1.终止在此节点的最大路径,首先是自己的值包含进去,然后如果终止在左或右子树的根节点的最大路径值大于0的话,加上这个值。
2.经过这个节点的最大值,很简单了,左右子树的端点最大值加上自己的值。
3.不经过此节点的最大值,直接查看左右子树中的这个值(如果有左右子树的话),还有左右子树的端点最大值。

这样最后就写出一个递归的算法。如何写成循环还没想好。

2013-1-18,更新了一个更简单的办法.

Question: Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

代码:

248ms过大集合

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Maxes{
public:
    int tmax;//max of terminated in self
    int pmax;//max of pass self
    int nmax;//max of non-relative to self
    Maxes() {tmax = pmax = 0; nmax = (1 << (sizeof(int) * 8 - 1));}
    inline int getMax() {
        int m = tmax;
        if(m < pmax) m = pmax;
        if(m < nmax) m = nmax;
        return m;
    }
};
class Solution {
public:
    Maxes maxPath(TreeNode *root) {
        Maxes m;
        if(NULL == root)
            return m;

        Maxes l = maxPath(root->left);
        Maxes r = maxPath(root->right);

        //tmax is the max value which terminated at this node
        //when all of it's children is negative, this is it's value
        //or add the max value terminated at it's children
        m.tmax = max(l.tmax,r.tmax);
        if(m.tmax < 0) m.tmax = 0;
        m.tmax += root->val;

        //pmax is the max value which is pass this node
        //that is it's value terminated at it's children (if have, or zero), add self value
        m.pmax = l.tmax + r.tmax + root->val;

        //nmax is the max value which not including current node
        if(root->left)
            m.nmax = l.getMax();
        if(root->right) {
            int rmax = r.getMax();
            if(m.nmax < rmax) m.nmax = rmax;
        }
        return m;
    }
    int maxPathSum(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        Maxes m = maxPath(root);
        int ma = m.getMax();
        return ma;
    }
};

Code rewrite at 2013-1-18, 266ms pass large set, simpler

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int _curMax;
    //return the max path ending in root
    //and refresh the _curMax with the path sum that go through from left to root to right child.
    int maxWithRoot(TreeNode *root) {
        if(NULL == root) return 0;
        int leftmax = maxWithRoot(root->left);
        int rightmax = maxWithRoot(root->right);

        //the max from left child to right child, accross from root
        int arcmax = root->val;
        if(leftmax > 0) arcmax += leftmax;
        if(rightmax > 0) arcmax += rightmax;
        if(_curMax < arcmax) _curMax = arcmax;

        //the max that end in root
        int pathmax = root->val;
        int submax = std::max(leftmax,rightmax);
        if(submax > 0) pathmax += submax;
        if(_curMax < pathmax) _curMax = pathmax;

        return pathmax;
    }
public:
    int maxPathSum(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        _curMax = INT_MIN;
        maxWithRoot(root);
        return _curMax;
    }
};

LeetCode题目:Binary Tree Level Order Traversal II

和上一题差不多,只不过最后输出的时候颠倒一下,另外:std::list才有push_front(),而std::vector没有这个方法。



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).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7]
  [9,20],
  [3],
]



代码:40ms过大集合

/**
 * 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 > levelOrderBottom(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        list > retTemp;

        queue trace;
        trace.push(root);
        trace.push(NULL);
        
        vector curLevel;
        while(true) {
            TreeNode *cur = trace.front();
            trace.pop();
            if(cur) {
                curLevel.push_back(cur->val);
                if(cur->left) trace.push(cur->left);
                if(cur->right) trace.push(cur->right);
            } else {
                if(curLevel.size()) {
                    retTemp.push_front(curLevel);
                    curLevel.erase(curLevel.begin(),curLevel.end());
                    trace.push(NULL);
                } else {
                    break;
                }
            }
        }
        
        vector > ret;
        for(list >::iterator it = retTemp.begin(); it != retTemp.end(); ++it) {
            ret.push_back(*it);
        }
        return ret;
    }
};

LeetCode题目:Binary Tree Level Order Traversal

题目简单,经典方法。只不过这题需要每一个level单独作为一个vector输出,因此在每一个level结束的时候插入一个NULL标记。每当遇到这个标记,就说明一层已经完全访问了。



Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:
[
[3],
[9,20],
[15,7]
]



代码:28ms过大集合

/**
 * 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 > levelOrder(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector > ret;
        if(NULL == root) return ret;
        queue trace;
        trace.push(root);
        trace.push(NULL);
        vector levelVals;
        while(true) {
            TreeNode *cur = trace.front();
            trace.pop();
            if(NULL == cur) {
                ret.push_back(levelVals);
                levelVals.erase(levelVals.begin(),levelVals.end());
                if(trace.size())
                    trace.push(NULL);
                else
                    break;
            } else {
                levelVals.push_back(cur->val);
                if(cur->left) trace.push(cur->left);
                if(cur->right) trace.push(cur->right);
            }
        }
        return ret;
    }
};



Code rewrite at 2012-12-22, 24ms pass the large test set

class Solution {
public:
    vector > levelOrder(TreeNode *root) {
        vector > ret;
        
        queue q;
        if(root) {
            q.push(root);
            q.push(NULL);
        }
        
        vector level;
        while(q.size()) {
            TreeNode *cur = q.front();
            q.pop();
            if(cur) {
                level.push_back(cur->val);
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            } else {
                ret.push_back(level);
                level.erase(level.begin(),level.end());
                if(q.size()) q.push(NULL);
            }
        }
        
        return ret;
    }
};

CCI题目4-1:Check Balance of a Binary Tree,二叉树的基本算法

这里我把题目理解为,任意两个叶子节点(左右子树都空)的深度不超过1.
那就计算一下一棵树的叶子节点中最大的深度和最小的深度,两者不超过1即可。

PS.但是按照书上的solution,代码翻译出来的题意,对于叶子节点的理解是说Null节点。



代码中还包含了这一部分的一些基本代码,包括:
1.从string初始化一棵树(借鉴leetcode的表示方法)
2.递归实现的inorder,preorder,postorder深度优先遍历
3.queue实现的广度优先遍历



题目
Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.



Code

<

pre>
//
// main.cpp
// CCI.4.1.Check Balance of a Tree
//
// Created by Qiu Xiangyu on 12-11-21.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

include

using namespace std;

struct TreeNode {
int value;
TreeNode *left;
TreeNode *right;
TreeNode(int val, TreeNode *l, TreeNode *r) {
value = val;
left = l;
right = r;
}
TreeNode(int val = 0) {
value = val;
left = NULL;
right = NULL;
}
};

TreeNode *buildTreeFromString(string s) {
if (s.size() == 0 || s[0] == ‘#’) {
return NULL;
}
TreeNode *root = NULL;
queue<TreeNode**> que;
que.push(&root);
int v = 0;
bool isnull = false;
int istr = 0;
while (true) {
if (istr >= s.size() || s[istr] == ‘,’) {

        TreeNode **ppnode = que.front();
        que.pop();

        if (ppnode && !isnull) {
            TreeNode *newNode = new TreeNode(v);
            *ppnode = newNode;
            que.push(&newNode->left);
            que.push(&newNode->right);
        } else {
            que.push(NULL);
            que.push(NULL);
        }

        if (istr >= s.size()) {
            break;
        }

        v = 0;
    } else {
        if (s[istr] == '#') {
            v = 0;
            isnull = true;
        } else {
            v = 10 * v + s[istr] - '0';
            isnull = false;
        }
    }
    ++istr;
}
return root;

}

void inorder(TreeNode root, void (nodeHandler)(TreeNode* node) ) {
if (root == NULL) {
cout<<“null\n”;
return;
}
inorder(root->left, nodeHandler);
nodeHandler(root);
inorder(root->right, nodeHandler);
}

void preorder(TreeNode root, void (nodeHandler)(TreeNode* node) ) {
if (root == NULL) {
cout<<“null\n”;
return;
}
nodeHandler(root);
preorder(root->left, nodeHandler);
preorder(root->right, nodeHandler);
}

void postorder(TreeNode root, void (nodeHandler)(TreeNode* node) ) {
if (root == NULL) {
cout<<“null\n”;
return;
}
postorder(root->left, nodeHandler);
postorder(root->right, nodeHandler);
nodeHandler(root);
}

void breadthfirst(TreeNode root, void (nodeHandler)(TreeNode* node)) {
queue<TreeNode*> que;
que.push(root);
int count = root ? 1 : 0;
while (que.size()) {
TreeNode *node = que.front();
que.pop();
if (node) {
–count;
nodeHandler(node);
que.push(node->left);
que.push(node->right);
if (node->left) {
++count;
}
if (node->right) {
++count;
}
} else {
cout<<“n\n”;
que.push(NULL);
que.push(NULL);
}
if (0 == count) {
break;
}
}
}

void printNode(TreeNode *node) {
cout<value<<endl;
}

int mindepth(TreeNode *node) {
if (NULL == node) {
return 0;
}
int rightMin = mindepth(node->right);
if (node->left) {
int leftMin = mindepth(node->left);
if (node->right) {
return 1 + (leftMin < rightMin ? leftMin : rightMin);
} else {
return 1 + leftMin;
}
} else {
return 1 + rightMin;
}
}
int maxdepth(TreeNode *node) {
if (NULL == node) {
return 0;
}
int leftmax = maxdepth(node->left);
int rightmax = maxdepth(node->right);
return 1 + (leftmax > rightmax ? leftmax : rightmax);
}
bool isBalance(TreeNode *root) {
int dmax = maxdepth(root);
int dmin = mindepth(root);
return abs(dmax – dmin) <= 1;
}
int main(int argc, const char * argv[])
{
// insert code here…
std::cout << “Hello, World!\n”;
string instr = “1,2,3,4,#,#,#,5”;
TreeNode *root = buildTreeFromString(instr);
breadthfirst(root, printNode);
int dmax = maxdepth(root);
int dmin = mindepth(root);
cout<<“dmax:”<<dmax<<“,dmin:”<<dmin<<endl;
cout<<“Is balance:”<<isBalance(root)<<endl;
return 0;
}

LeetCode题目:Unique Binary Search Trees II

上一题可以用简单的办法算出了,这道题要输出所有可能的二叉树,就只能一个一个构造了。
写了一个递归的算法,114ms过了大测试集合



Unique Binary Search Trees II
Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n.
For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.



代码:114ms过大集合

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    TreeNode *copyTree(TreeNode *root) {
        if(NULL == root) return NULL;
        TreeNode *croot = new TreeNode(root->val);
        croot->left = copyTree(root->left);
        croot->right = copyTree(root->right);
        return croot;
    }
    vector generateTrees(int startval,int endval) {
        vector ret;
        if(endval < startval) {
            ret.push_back(NULL);
        }
        else {
            for(int rootval = startval; rootval <= endval; ++rootval) {
                vector temp;
                {//push root into ret
                    TreeNode *root = new TreeNode(rootval);
                    temp.push_back(root);
                }
                //process the left subtrees
                vector lefts = generateTrees(startval, rootval - 1);
                int count = temp.size();
                for(int ti = 0; ti < count; ++ti) {
                    TreeNode *root = temp[0];
                    temp.erase(temp.begin());
                    for(int li = 0; li < lefts.size(); ++li) {
                        TreeNode* left = lefts[li];
                        TreeNode *newroot = copyTree(root);
                        newroot->left = left;
                        temp.push_back(newroot);
                    }
                    //if(root) delete root;
                }
                //process the right subtrees
                vector rights = generateTrees(rootval + 1, endval);
                count = temp.size();
                for(int ti = 0; ti < count; ++ ti) {
                    TreeNode *root = temp[0];
                    temp.erase(temp.begin());
                    for(int ri = 0; ri < rights.size(); ++ri) {
                        TreeNode *copyExpand = copyTree(root);
                        copyExpand->right = rights[ri];
                        temp.push_back(copyExpand);
                    }
                    //if(root) delete root;
                }
                for(int i = 0; i < temp.size(); ++i) {
                    ret.push_back(temp[i]);
                }
            }
        }
        return ret;
    }
public:
    vector generateTrees(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return generateTrees(1,n);
    }
};

LeetCode题目:Symmetric Tree

从根开始,迭代查看左子树和右子树是否是对称的。
其中左子树和右子树对称的条件(均非空条件下)是:

  1. 两个节点值相等
  2. 左节点的左子树和右节点的右子树对称
  3. 左节点的右子树和右节点的左子树对称

这样就很容易写出来递推的算法。



Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.



迭代算法,44ms过大集合

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode *left, TreeNode *right) {
        if(left == NULL) {
            return right == NULL;
        } else {
            if (right == NULL)
                return false;
            else {
                if(left->val != right->val) {
                    return false;
                }
                if(!isSymmetric(left->right,right->left)) {
                    return false;
                }
                if(!isSymmetric(left->left, right->right)) {
                    return false;
                }
                return true;
            }
        }
    }
    bool isSymmetric(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(NULL == root) return true;
        return isSymmetric(root->left,root->right);
    }
};

LeetCode题目:Recover Binary Search Tree

分析
题目说在一棵二叉搜索树中有两个节点位置错了,要在常数空间将其改正。
想到的算法就是中序遍历二叉树,找到这一对错误的节点,之后交换它们的值。
如何找到这一对节点呢?
这一对节点先出现的那个肯定是比其中序后继大的,后出现的那个节点的后继,肯定不大于先出现这个错误节点的值。
但是中序遍历二叉树的空间复杂度是O(logN)啊,如何做到常数,目前还没想到。

<br>
Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.



代码:368ms过大集合

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode *root) {
        vector trace;
        TreeNode *cur = root;
        //find the lest node in the BST
        while(cur->left) {
            trace.push_back(cur);
            cur = cur->left;
        }
        TreeNode *wrong0 = NULL;//first wrong node
        TreeNode *wrong1 = NULL;//last wrong node
        while(true){
            TreeNode *next = NULL;
            //find the next inorder node
            if(cur->right){
                //if cur have right child, the next inorder node is the most left node in this sub-tree
                trace.push_back(cur);
                next = cur->right;
                while(next->left){
                    trace.push_back(next);
                    next = next->left;
                }
                if(!wrong0 && cur->val > next->val) {
                    wrong0 = cur;
                } else if(wrong0 && wrong0->val <= next->val) {
                    wrong1 = cur;
                    break;
                }
                cur = next;
            } else {
                //if cur have no right child, the next inorder nodt is the most near parant which cur belong to it's left sub-tree
                TreeNode *tempCur = cur;
                while(trace.size()) {
                    TreeNode *tempPar = trace.back();
                    if(tempPar->left == tempCur) {
                        next = tempPar;
                        break;
                    }
                    tempCur = tempPar;
                    trace.pop_back();
                }
                if(next) {
                    if(!wrong0 && cur->val > next->val) {
                        wrong0 = cur;
                    } else if(wrong0 && wrong0->val <= next->val) {
                        wrong1 = cur;
                        break;
                    }
                    cur = next;
                }
            }
            if(!next) break;
        }
        if(!wrong1) wrong1 = cur;
        int temp = wrong0->val;
        wrong0->val = wrong1->val;
        wrong1->val = temp;
    }
};



Code rewrite at 2013-1-18, 388ms pass large set, more clear

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(NULL == root) return;
        TreeNode *firstNode = NULL, *secondNode = NULL;
        
        //find first node, with inorder traversal
        stack trace;
        if(root) trace.push(root);
        bool forward = true;
        TreeNode *pre = NULL;
        TreeNode *lastNode = NULL;
        while(trace.size()) {
            TreeNode *cur = trace.top();
            if(forward) {
                if(cur->left && cur->left != pre) {
                    trace.push(cur->left);
                } else {
                    forward = false;
                }
            } else {
                if(pre != cur->right) {
                    if(lastNode && lastNode->val > cur->val) {
                        firstNode = lastNode;
                        break;
                    }
                    lastNode = cur;
                }
                if(cur->right && cur->right != pre) {
                    trace.push(cur->right);
                    forward = true;
                } else {
                    trace.pop();
                }
            }
            pre = cur;
        }
        if(NULL == firstNode) return;
        
        //find second node, in reverse order of inorder traversal
        while(trace.size()) trace.pop();
        if(root) trace.push(root);
        forward = true;
        pre = NULL;
        lastNode = NULL;
        while(trace.size()) {
            TreeNode *cur = trace.top();
            if(forward) {
                if(cur->right && cur->right != pre) {
                    trace.push(cur->right);
                } else {
                    forward = false;
                }
            } else {
                if(pre != cur->left) {
                    if(lastNode && lastNode->val < cur->val) {
                        secondNode = lastNode;
                        break;
                    }
                    lastNode = cur;
                }
                if(cur->left && cur->left != pre) {
                    trace.push(cur->left);
                    forward = true;
                } else {
                    trace.pop();
                }
            }
            pre = cur;
        }
        if(NULL == secondNode) return;
        
        //swap
        int t = firstNode->val;
        firstNode->val = secondNode->val;
        secondNode->val = t;
        
    }
};

LeetCode题目:Binary Tree Inorder Traversal

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?
confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

    代码

    /**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    
  1. 递归解法
    很简单,8ms过小集合,12ms过大集合

    class Solution {
    public:
        vector inorderTraversal(TreeNode *root) {
            vector result;
            if (NULL == root)
                return result;
            vector leftResult = inorderTraversal(root->left);
            vector rightResult = inorderTraversal(root->right);
            for( int i = 0 ; i < leftResult.size(); ++i)
                result.push_back(leftResult[i]);
            result.push_back(root->val);
            for( int i = 0 ; i < rightResult.size(); ++i)
                result.push_back(rightResult[i]);
            return result;
        }
    };
    
  2. 循环解法
    稍复杂点,大小集合都是8ms过

    class Solution {
    public:
        vector inorderTraversal(TreeNode *root) {
            vector result;
            
            vector trace;
            TreeNode *cur = root;
            TreeNode *pre = NULL;
            bool forward = true;
            while(cur)
            {
                if (forward) 
                {
                    //have unvisited left
                    if (cur->left && pre != cur->left)
                    {
                        pre = cur;
                        trace.push_back(cur);
                        cur = cur->left;
                        continue;
                    }
                    forward = false;
                }
                else
                {
                    //not return from right, add self
                    if(cur->right == NULL || cur->right != pre)
                        result.push_back(cur->val);
                    //go right if could
                    if(cur->right && pre != cur->right)
                    {
                        forward = true;
                        pre = cur;
                        trace.push_back(cur);
                        cur = cur->right;
                        continue;
                    }
                    //go up
                    pre = cur;
                    if (trace.size() > 0)
                    {
                        cur = trace[trace.size() - 1];
                        trace.pop_back();
                    } else
                        cur = NULL;
                    
                }
            }
            
            return result;
        }
    };
    
  3. 循环解法,2012年12月6日重写,比上一个简洁
    class Solution {
    public:
        vector inorderTraversal(TreeNode *root) {
            // Start typing your C/C++ solution below
            // DO NOT write int main() function
            vector ret;
            if(NULL == root) return ret;
            
            bool forward = true;
            stack trace;
            TreeNode *preNode = NULL;
            trace.push(root);
            
            while(trace.size()) {
                TreeNode *curNode = trace.top();
                if(forward) {
                    if(curNode->left && preNode != curNode->left) {
                        trace.push(curNode->left);
                    } else {
                        //no left or left visited
                        forward = false;
                    }
                } else {
                    //backward, find sibling(right child)
                    //if not back from right child, then visit it
                    if(curNode->right != preNode)
                        ret.push_back(curNode->val);
                    if(curNode->right && preNode != curNode->right) {
                        //if have an unvisited right child, traval it.
                        trace.push(curNode->right);
                        forward = true;
                    } else {
                        //all sub-tree of this node is visited
                        trace.pop();
                    }
                }
                preNode = curNode;
            }
            
            return ret;
        }
    };