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;
}
网友评论