Tag: 二叉树

思路

title真是长..给前序遍历和中序遍历，构造二叉树。
前序遍历就是Node, Left, Right，而中序遍历是Left, Node, Right，因此给一个前序遍历的序列，他的第一个节点肯定就是那个Node，然后在中序序列里找，就能把序列分成左中右三部分。
自然地就要用递归啦~

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTreeSub(const vector<int>& preorder, int p_start, int p_end,
                            const vector<int>& inorder, int i_start, int i_end){
        int pivot = preorder[p_start];
        TreeNode* root = new TreeNode(pivot);
        int indexPivotInorder = -1;
        for(indexPivotInorder=i_start; indexPivotInorder<=i_end; indexPivotInorder++){
            if(inorder[indexPivotInorder] == pivot)
                break;
        }
        int len_left = indexPivotInorder-i_start;
        if(indexPivotInorder > i_start){
            //if we still have left part
            root->left = buildTreeSub(preorder, p_start+1, p_start+len_left, inorder, i_start, indexPivotInorder-1);
        }
        if(indexPivotInorder < i_end){
            //if we still have right part
            root->right = buildTreeSub(preorder, p_start+len_left+1, p_end, inorder, indexPivotInorder+1, i_end);
        }
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty() || inorder.empty())
            return NULL;
        return buildTreeSub(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
    }
};

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,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

思路

记住上一行的输出（结果）节点，每一次从后往前读出下一行，这样第2,4,6次读的时候其实就会翻转成正向了。唯一的问题是左右子节点写入下一行的顺序，按照当前顺序区分一下就行。不是左右左右，就是右左右左，具体看code吧。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(root == NULL)
            return result;
        vector<TreeNode*>* currRow = new vector<TreeNode*>();
        vector<TreeNode*>* nextRow = new vector<TreeNode*>();
        bool direction = true;  //true: R,L,R,L,...; false:L,R,L,R,...
        currRow->push_back(root);
        while(!currRow->empty()){
            //Output current row
            vector<int> currRowResult;
            for(int i=0; i<currRow->size(); i++){
                currRowResult.push_back( (*currRow)[i]->val );
            }
            result.push_back(currRowResult);
            //
            for(int i=currRow->size()-1; i>=0; i--){
                TreeNode* currNode = (*currRow)[i];
                if(direction){
                    if(currNode->right != NULL)
                        nextRow->push_back(currNode->right);
                    if(currNode->left != NULL)
                        nextRow->push_back(currNode->left);
                } else {
                    if(currNode->left != NULL)
                        nextRow->push_back(currNode->left);
                    if(currNode->right != NULL)
                        nextRow->push_back(currNode->right);
                }
            }
            //swap currRow and nextRow
            vector<TreeNode*>* temp = currRow;
            currRow = nextRow;
            nextRow = temp;
            nextRow->clear();
            direction = !direction;
        }
        return result;
    }
};

思路

发现是一个树的遍历的题目，而且题目限制的比较死，是个满二叉树，这样处理的时候就避免了比较烦人的跨树指针的情况。比如下面这种建立4->5的指针：

    1
  2   3
4    5  6

第一时间想到的解法是弄个工作队列，然后一层一层遍历下去就行了，这个解法的空间复杂度是O(n)，不符合题目要求。后来再一想，其实既然上一层已经把下一层的next指针建立好了，就不用再从工作队列里去“回忆”了，只要在每一行的开头记住下一行在哪里就行，这样只要O(1)空间复杂度。
另外是如何设置next指针，一共有两个情况：

1. node自己的左孩子和右孩子连起来
2. node的右孩子与node右侧节点它的左孩子连起来

代码

O(n)空间复杂度方法

/**
 * 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) {
        queue<TreeLinkNode*> workingQ;
        if(root == NULL)
            return;
        workingQ.push(root);
        while(!workingQ.empty())
        {
            TreeLinkNode* node = workingQ.front();
            workingQ.pop();
            if(node->left == NULL || node->right == NULL)
                continue;   //Leaf node
            node->left->next = node->right; //Inner connection
            if(node->next != NULL)
                node->right->next = node->next->left; //Outter connection
            workingQ.push(node->left);
            workingQ.push(node->right);
        }
    }
};

O(1)空间复杂度方法

class Solution {
public:
    void connect(TreeLinkNode *root) {
        TreeLinkNode* nextRowPtr = root;
        TreeLinkNode* node = root;
        bool atRowStart = true;
        while(nextRowPtr != NULL)
        {
            if(node->left == NULL || node->right == NULL)
                break;   //Leaf node
            if(atRowStart)
            {
                atRowStart = false;
                nextRowPtr = node->left;
            }
            node->left->next = node->right; //Inner connection
            if(node->next != NULL)
            {
                node->right->next = node->next->left; //Outter connection
                node = node->next;
            }
            else
            {
                node = nextRowPtr;
                atRowStart = true;  //End of current row
            }
        }
    }
};

如家网络实在太卡了，不过还好没有人劫@!$#@W…
稍微说一下思路把，这个问题就是判断某一层上的节点它的孩子会不会“溢出”，或者第一层的节点有没有完全闭合。我用一个栈来保存每一层的孩子数目（包括null）：

• 当碰到数字的时候，压一层计数为0的栈，表示新开了一层并且这一层的孩子数为0
• 当碰到#号时，说明多了一个空孩子，当前栈顶的计数+1，并且判断当前栈顶的计数是否>=2了，如果是的话，那说明这一层已经满了，那就退栈，然后再继续给新栈顶计数+1，继续判断是否满….如此往复

由于有了#表示空节点所以层级变得明确，举个例子：一个叶节点读入两个#，当前层的计数等于2后就退栈，并且给父亲层的计数器+1（表示下一层已经结束了，父亲多了一个左/右孩子）。
代码（好久没有纯手打一遍AC了）

class Solution {
public:
    bool isValidSerialization(string preorder) {
        int size = preorder.size();
        stack<int> working;
        int i = 0;
        while(i < size){
            int end = preorder.find(',', i);
            if(end == string::npos)
                end = size;
            if(preorder[i] != '#'){
                //number
                working.push(0);
            } else {
                //'#'
                if(i == 0){
                    //The null root?!
                    if(size > 1) return false;
                    else return true;
                }
                working.top() += 1;
                while(working.size()>1 && working.top() >= 2){
                    working.pop();
                    working.top() += 1;
                }
            }
            if(working.size() == 1 && working.top() > 2)
                return false;
            i = end+1;
        }
        return (working.size()==1) && (working.top()==2);
    }
};

BTW,苏州的交通状况和路面比杭州好多了。

题目

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

思路1

找两个节点的公共最小祖先，可以利用递归的思想，即假设我们有个函数，能判断root为根节点的子树里有几个符合的节点（0，1或2个），在递归跳出的过程中，一旦我们发现有返回2个节点的，那这个根元素就肯定是p和q的最低公共节点了。

思路2

假设要找的节点是5和1，那么从根节点通往5的路径是3->5，通往1的路径是3->1。可以用递归方法构造一个路径栈，比较容易地找到路径，然后就变成两条路径的最长公共节点的问题了，“分岔”的地方就是LCA.
相比思路1，这个方法实施起来简单一些，但是要遍历两遍树，会稍微慢一点。

代码1

* struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int LCASub(TreeNode* root, TreeNode* p, TreeNode* q, TreeNode*& retNode){
        //If we find p or q, return 1
        //If we find root contains p and q, return 2 and set the retNode to common node
        //Else return 0
        if(root == NULL)
            return 0;
        int leftRet = LCASub(root->left, p, q, retNode);
        if(leftRet == 2)
            return 2;
        int rightRet = LCASub(root->right, p, q, retNode);
        if(rightRet == 2){
            return 2;
        }
        if(leftRet + rightRet == 2){
            retNode = root;
            return 2;
        } else if(root == p || root == q){
            if(leftRet==1 || rightRet == 1){
                retNode = root;
                return 2;
            } else {
                return 1;
            }
        } else {
            return leftRet + rightRet;
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* retVal = NULL;
        LCASub(root, p, q, retVal);
        return retVal;
    }
};

代码2

class Solution {
public:
    bool getPath(TreeNode* root, TreeNode* p, stack<TreeNode*>& path){
        //Get path from root to p
        //If not available, return false
        if(root == NULL || root == p){
            path.push(root);
            return true;
        }
        bool foundPath = false;
        if(root->left != NULL){
            //try left
            foundPath = getPath(root->left, p, path);
            if(foundPath){
                //Mission complete, push current node and return
                path.push(root);
                return true;
            }
        }
        if(root->right != NULL){
            foundPath = getPath(root->right, p, path);
            if(foundPath){
                path.push(root);
                return true;
            }
        }
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> pPath;
        stack<TreeNode*> qPath;
        getPath(root, p, pPath);
        getPath(root, q, qPath);
        TreeNode* result = NULL;
        while(!pPath.empty() && !qPath.empty()){
            if(pPath.top() != qPath.top())
                break;
            result = pPath.top();
            pPath.pop();
            qPath.pop();
        }
        return result;
    }
};