二叉树深度遍历
中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
//创建一个答案数组
List<Integer> ans = new ArrayList<>();
//创建一个双向链表，用作栈
Deque<TreeNode> stk = new LinkedList<>();
//当栈不空或者root不是null时
while(root != null || stk.isEmpty()){
//将所有左子节点入栈，找到没有左子树的节点为止
while(root != null){
stk.push(root);
root = root.left;
}
//当栈不空时，弹出栈顶元素，该节点就是遍历到的节点，将其加入答案数组，并转向该节点的右子树
/**
*分析：为什么直接令root = tmp.right正确
*1. tmp.right==null时 进入下一个循环时，回直接弹出栈顶
*元素（该节点的父节点）
*2. tmp.right!=null时，说明该遍历该节点的右子树了，当
*右子树遍历完成后，在弹出的节点还是该节点的父节点；
*/
while (stk.isEmpty()){
TreeNode tmp = stk.pop();
ans.add(tmp.val);
root = tmp.right;
}
}
return ans;
}
前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
//同上
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> stk = new LinkedList<>();
//同上
while(root != null || !stk.isEmpty()){
//找到最左节点，不同的是，边找，边将节点加入答案，因为前序遍历就是这样的
while(root != null){
stk.push(root);
ans.add(root.val);
root = root.left;
}
//栈不空，弹出栈顶元素，此时，这个元素已经被遍历过了，我们直接令他等于他的右子树，接着遍历，如果没有右子树的话，进入下一个循环，又会弹出栈顶元素；
if(!stk.isEmpty()){
root = stk.pop();
root = root.right;
}
}
return ans;
}
后序遍历 重点 ★
public List<Integer> postorderTraversal(TreeNode root) {
//解法一：利用前序遍历的性质：根->左子树->右子树，可以发现，如何我们将其反转，就变成了右子树-》左子树-》根；和后序遍历很接近，后序遍历：左子树-》右子树-》根；我们只需将前序遍历改为根-》右子树-》左子树；再反转就得到了后序遍历；
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> stk1 = new LinkedList<>();
Deque<TreeNode> stk2 = new LinkedList<>();
while(root != null || !stk1.isEmpty()){
while(root != null){
stk2.push(root);
stk1.push(root);
root = root.right;
}
if(!stk1.isEmpty()){
root = stk1.pop();
root = root.left;
}
}
while (!stk2.isEmpty()){
ans.add(stk2.pop().val);
}
return ans;
//-----------------------------------------------------------------------------------------------------------------
//解法二：
//创建答案数组和双向链表栈
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> stk = new LinkedList<>();
//增加一个prev节点，指向上一个遍历到的节点
TreeNode prev = null;
if (root == null)
return ans;
while(root != null || !stk.isEmpty()){
//同样的先将左子节点全部入栈
while(root != null){
stk.push(root);
root = root.left;
}
//把栈顶元素抛出来
root = stk.pop();
//判断这个节点是不是下一个该遍历的节点
//判断条件是该节点的右子树是不是null或者上一个遍历的节点prev
//如果是，则将prev指向该节点，并将root指向null（为了下一次循环时直接抛出栈顶元素，避免重复遍 //历左子树）
if(root.right == null || root.right == prev){
ans.add(root.val);
prev = root;
root = null;
}else{
//如果不是，则将该节点重新入栈，并将root指向其右子树，因为如果其不是的话必定有右子树，且没 //有遍历到；
stk.push(root);
root = root.right;
}
}
return ans;