［抄题］：二叉树前序遍历
［思维问题］：
不会递归。三要素：下定义、拆分问题（eg root-root.left）、终止条件
［一句话思路］：
节点非空时往左移，否则新取一个点 再往右移。
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
不要提起加入root节点。
［二刷］：
［三刷］：
［四刷］：
［五刷］：
［总结］：
［复杂度］：Time complexity: O(n) Space complexity: O(n) (lgn for B-BST)
［英文数据结构，为什么不用别的数据结构］：
［其他解法］：
［Follow Up］：
［LC给出的题目变变变］：
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/ public class Solution {
/*
* @param root: A Tree
* @return: Preorder in ArrayList which contains node values.
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root; if (root == null) {
return result;
} while (!stack.isEmpty() || p != null) {
if (p != null) {
stack.push(p);
result.add(p.val);
p = p.left;
}
else {
p = stack.pop();
p = p.right;
}
}
return result;
}
}
［抄题］：二叉树中序遍历
［思维问题］：
不会递归。三要素：下定义、拆分问题（eg root-root.left）、终止条件
［一句话思路］：
左边走完了再放数
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
［二刷］：
［三刷］：
［四刷］：
［五刷］：
［总结］：
［复杂度］：Time complexity: O(n) Space complexity: O(n)
［英文数据结构，为什么不用别的数据结构］：
stack先进先出
［其他解法］：
遍历法：先写主函数，再写遍历函数
分治法：分开的时候要调用函数：left = 函数（root.left）
［Follow Up］：
［LC给出的题目变变变］：
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/ public class Solution {
/*
* @param root: A Tree
* @return: Preorder in ArrayList which contains node values.
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root; if (root == null) {
return result;
} while (!stack.isEmpty() || p != null) {
if (p != null) {
stack.push(p);
p = p.left;
}
else {
p = stack.pop();
result.add(p.val);
p = p.right;
}
}
return result;
}
}
［抄题］：二叉树后序遍历
［思维问题］：
不会递归。三要素：下定义、拆分问题（eg root-root.left）、终止条件
［一句话思路］：
前序遍历全都反过来：节点添加顺序、提前添加用
result.addFirst ［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
［二刷］：
［三刷］：
［四刷］：
［五刷］：
［总结］：
［复杂度］：Time complexity: O() Space complexity: O()
［英文数据结构，为什么不用别的数据结构］：
［其他解法］：
［Follow Up］：
［LC给出的题目变变变］：
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> result = new LinkedList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
result.addFirst(p.val); // Reverse the process of preorder
p = p.right; // Reverse the process of preorder
} else {
TreeNode node = stack.pop();
p = node.left; // Reverse the process of preorder
}
}
return result;
}