RTTO WEEK5

• WEEK 5
  • 144.二叉树的前序遍历（e）
  • 94.二叉树的中序遍历（e）
  • 145.二叉树的后序遍历（e）
  • 非递归遍历的统一写法
  • 102.二叉树的层序遍历（m）
  • 226.反转二叉树（e）
  • 101.对称二叉树（e）
  • 559.N叉树的最大深度（e）
  • 111.二叉树的最小深度（e）
  • 222.完全二叉树的节点个数（m）

WEEK 5

144.二叉树的前序遍历（e）

递归法：中左右

非递归法：

1、使用栈结构

先pop根节点，push右节点，push左节点

94.二叉树的中序遍历（e）

递归法：左中右

非递归法：

1、使用栈结构和指针

指针动态记录需要最先出栈的左节点位置，先找到最下层的左节点，并将途径的节点入栈，找到该左节点后存入res，并pop，此时栈中的top元素为该左节点的根节点，pop根节点后去寻找是否右节点直至栈空。

145.二叉树的后序遍历（e）

递归法：左右中

非递归法：

1、类似前序遍历

先pop根节点，push左节点，push右节点，最后reverse结果

非递归遍历的统一写法

中序为例

如何理解？

目的是使在res数组中进行push_back最终值的时候，必须碰到栈中的NULL，才加入到结果集；

无论什么遍历顺序都是以根节点访问状态为关键，那些访问到但还没处理的根节点就加入空节点作为标记，代表着下次栈中top遇到标记时可以加入到结果集。

前序 后序只需改变push 中节点和NULL节点的位置就行。

102.二叉树的层序遍历（m）

递归法：

第二行是res容器的扩容，注意输出的数据形式！

非递归法：

用队列实现

中左右（若有）入队 ，出队入结果集。

226.反转二叉树（e）

递归法：

swap(root->left, root->right);

非递归法：使用栈结构

在非递归遍历的基础上修改；存结果数组改为交换左右子树。

101.对称二叉树（e）

递归法：

1.确定递归函数的参数和返回值。

需要比较两个子树是否对称，故参数为左子树和右子树的节点；参数为bool。

2.确定终止条件。

首先排除空指针的情况：

左右空 true

左右一空 false

左右值不等 false

3.确定单层递归的逻辑。

如图对称二叉树为最后一层3-3 4-4相等

非递归方法：

使用队列（此时的规则非前中后遍历了）

需要按题目规则两两入队比较是否相等；false的判断条件和递归法的一样，左右有空或者左右值不相等；保证每次成对push的节点是需要进行比较的节点。（用栈也行）

559.N叉树的最大深度（e）

和上题一样，只不过Node数据结构变了，加个遍历儿子节点就行。

111.二叉树的最小深度（e）

递归法：

1.递归参数和返回值：参数为node 返回值为int

2.终止条件：node为空终止

3.单层逻辑：左存在 右不存在 说明需要更新左边的深度 +1；右存在 左不存在 说明需要更新右边的深度 +1

非递归法：

使用层序遍历，若左右都无节点就说明到了最低点，若有左右其中一个节点则不是最低点；

222.完全二叉树的节点个数（m）

递归法：

class Solution {
public:
  int getNodesNum(TreeNode* node){
	if(node == NULL) return 0;
	int leftNum = getNodesNum(node->left);
	int rightNum = getNodesNum(node->right);
	int treeNum = leftNum + rightNum + 1;
	return treeNum;
  }

  int countNodes(TreeNode* root) {
      return getNodesNum(root);
  }
};

非递归法：

层序遍历