144. 二叉树的前序遍历

前序遍历：先根后左再右
思路：

  1. 根节点起，输出根，判左
  2. 左存在，则左作为根，回到1
  3. 左不存在，判右
  4. 右存在，则右作为根，回到1
  5. 右不存在，回到上一个根节点，回到1

总结：先将根加入集合，然后遍历左节点并入栈，左节点为空则出栈，遍历右节点。
public List preorderTraversal(TreeNode root) {
List result = new ArrayList<>();
while (!treeNode.isEmpty() || root != null) {
while (root != null) {
result.add(root.val);
treeNode.push(root);
root = root.left;
}
root = treeNode.pop();
root = root.right;
}
return result;
}

94.二叉树的中序遍历

中序遍历：先左后根再右
思路：

  1. 根节点起，判左是否存在节点
  2. 左存在，则左作为根，回到1
  3. 左不存在，输出根，并判右
  4. 右存在，则右作为根，回到1
  5. 右不存在，回到上一个根节点，并判右，回到4

总结：先将左节点遍历入栈，左节点为空则出栈，将左节点作为根加入集合，再遍历右节点。
public List inorderTraversal(TreeNode root) {
List result = new ArrayList<>();
this.leftHelp(root);
while (hasNext()) {
result.add(this.next());
}
return result;
}
public void leftHelp(TreeNode root) {
while (root != null) {
this.treeNode.push(root);
root = root.left;
}
}

public int next() {
TreeNode topmostNode = this.treeNode.pop();
if (topmostNode.right != null) {
this.leftHelp(topmostNode.right);
}
return topmostNode.val;
}

public boolean hasNext() {
return this.treeNode.size()>0;
}

145.二叉树的后序遍历

后序遍历：先左后右再根
思路：

  1. 根入，判左
  2. 左存在，则左作为根，回到1
  3. 左不存在，判右
  4. 右存在，则右作为根，回到1
  5. 右不存在，输出根，回到上一个根节点，并判右，回到4

注意：右不存在回到上一个根节点时，需要判断右是否已输出，若输出了则不需要进行右判断了，直接输出。
总结：遍历左节点入栈，左节点为空则出栈，将左节点加入集合，随后遍历右节点，若根的右节点为空或根的右节点的值已加入集合，则将根加入集合
public List postorderTraversal(TreeNode root) {
List result = new ArrayList<>();
TreeNode item = null;
this.leftHelp(root);
while (!treeNode.isEmpty()) {
TreeNode top = treeNode.pop();
if (top.right == null || top.right == item) {
result.add(top.val);
item = top;
} else {
treeNode.push(top);
this.leftHelp(top.right);
}
}
return result;
}