II199.二叉树的右视图637.二叉树的层平均值429.N叉树的层序遍历515.在每个树行中找最大值116.填充每个节点的下一个右侧节点指针117.填充每个节点的下一个右侧节点指针II104.二叉树的最大深度111.二叉树的最小深度

226.翻转二叉树101.对称二叉树

只使用二叉树结构无法层序遍历。

因为当你遍历到一个某个节点左节点时无法遍历到其右节点。

需要一个其他结构来辅助。

选择使用队列queue保存每一层待遍历的元素。

class

que.size();//用于记录弹出节点个数就是每层节点个数while

(size--)

que.front();que.pop();res1.push_back(cur-val);//记录节点数值if

(cur-left)

que.push(cur-right);//右节点入队列}res.push_back(res1);}return

res;}

res.push_back(vectorint());//开辟一个空的vectorint

(res.size()

res.emplace_back();等价于上一行res[depth].push_back(cur-val);recursive(cur-left,

res,

1);//depth1是回溯recursive(cur-right,

res,

0;//给res二维数组用来赋外层索引recursive(root,

res,

因为节点遍历只能从根节点开始。

所以就正常层序遍历最后结果反转一下。

class

que.front();que.pop();res1.push_back(cur-val);if

(cur-left)

que.push(cur-right);}res.push_back(res1);}reverse(res.begin(),

res.end());return

res.emplace_back();res[depth].emplace_back(root-val);recursion(root-left,

res,

1);//depth1是回溯recursion(root-right,

res,

res.emplace_back(root-val);//先加入右节点元素因为是保存右节点recursion(root-right,

res,

1);//depth1是回溯recursion(root-left,

res,

que.push(cur-right);}res.push_back(sum

cnt);}return

que.front();que.pop();res1.push_back(cur-val);for

(auto

{que.push(i);}}res.push_back(res1);}return

res;}

que.push(cur-right);}res.push_back(maxValue);}return

res;}

que.front();//如果不是最后一个与下一个节点相连if

(cur-left)

que.push(cur-right);}res;}return

res;}

root-right);//中invertTree(root-left);//左invertTree(root-right);//右return

root;}

nullptr;invertTree(root-left);//左invertTree(root-right);//右swap(root-left,

root;}

nullptr;invertTree(root-left);//左swap(root-left,

root-right);//中//因为上一行代码已经处理过左树处理完换成右树//接下来要处理的是原来的右树但是已经变成左树了invertTree(root-left);//右return

root;}

st.push(cur-left);//左st.push(cur);//中st.push(nullptr);}

else

st.top();st.pop();swap(cur-left,

cur-right);}}return

st.push(cur-right);//右st.push(cur);//中st.push(nullptr);if

(cur-left)

st.top();st.pop();swap(cur-left,

cur-right);}}return

{st.push(cur);st.push(nullptr);if

(cur-right)

st.top();st.pop();swap(cur-left,

cur-right);}}return

que.front();que.pop();swap(cur-left,

cur-right);if

因为是先判断左右是否对称再将结果传给中。

顺序为左右中。

所以是后序遍历。

class

false;第一个if判断了同时为空的条件满足条件执行return。

如果执行到第二条if语句表示第一个if一定失效即cur1和cur2不可能同时为空有cur1为空则cur2不为空cur1不为空则cur2为空所以第二个if只需要判断cur1不为空cur2一定为空或者cur2不为空cur1一定为空即可。

重要的是这两条if不能颠倒顺序。

(!cur1

false;也就是上面三条if可以用两条if来代替。

因为第二条的if中的cur2和第三条if中的cur1一定是非空的是多余的。

)再写if(

st;st.push(root-left);st.push(root-right);while

(!st.empty())

false;st.push(leftNode-left);st.push(rightNode-right);st.push(leftNode-right);st.push(rightNode-left);}return

true;}