LeetCode 树[L1]B篇

606. 根据二叉树创建字符串

    string res="";
    string tree2str(TreeNode* t) {
        if(t==NULL) return res;
        res.append(to_string(t->val));
        if(t->left||t->right)//只要两侧有一侧非空就要向左子树打上括号
        {
            res.append("(");
            tree2str(t->left);
            res.append(")");
        }
        if(t->right)//对右子树的递归，只有右子树非空才能打上括号。
        {
            res.append("(");
            tree2str(t->right);
            res.append(")");
        }
        return res;

对于这类打上括号的问题

分治

---

653. 两数之和 IV - 输入 BST

中序遍历在递增序列中检查是否含有两数之和

如果当前两元素之和小于 k，则更新 l 指向下一个元素。这是因为当我们需要增大两数之和时，应该增大较小数。

如果当前两元素之和大于 k，则更新 r 指向上一个元素。这是因为当我们需要减小两数之和时，应该减小较大数。

    vector<int>vt;
    void inorder(TreeNode* root)
    {
        if(root==NULL)  return ;
        inorder(root->left);
        vt.push_back(root->val);
        inorder(root->right);
    }
    bool findTarget(TreeNode* root, int k) {
        inorder(root);
        int l=0,r=vt.size()-1;
        while(l<r)
        {
            if(vt[l]+vt[r]==k)
                return true;
            else if(vt[l]+vt[r]<k)
                l++;
            else if(vt[l]+vt[r]>k)
                r--;
        }
        return false;
    }

---

589. N叉树的前序遍历

对于递归遍历。

 vector<int>vt;
    void pre(Node* root)
    {
        if(root==NULL)  return ;
        vt.push_back(root->val);
        for(int i=0;i<root->children.size();i++)
        {
            Node* temp=root->children[i];
            pre(temp);
        }
    }
    vector<int> preorder(Node* root) {
        if(root==NULL)  return vt;
        pre(root);
        return vt;
    }

关键在于如何每次处理完一个节点后，马上处理它的左边第一个子结点。

考虑一下层序遍历，如何由此向前序遍历的方向靠呢？
看一下队尾，如果结点每次都从队尾出列，然后再将子结点从左到右入列，很容易发现，这是一种根->右->左的前序遍历。
如果把入列方式改为将子结点从右到左入列，再每次都从队尾出列，这就是根->左->右的前序遍历。
此外，若每次从队尾出列，属于后进先出，相当于栈，则可用栈代替队列。

 vector<int> preorder(Node* root) {
    vector<int>vt;
    if(root==NULL)  return vt;
    stack<Node*>st;
    st.push(root);
    while(!st.empty())
    {
         Node* top=st.top();
         st.pop();
         vt.push_back(top->val);
         int n=(top->children).size();
         for(int i=n-1;i>=0;i--)
         {
             if(top->children[i])   
                st.push(top->children[i]);
         } 
    }
    return vt;
    }