递归遍历
思路：使用递归的方式比较简单。
1、递归函数的传参：因为最后输出一个数组，所以需要传入根节点和一个容器，本来想写数组，但发现长度不能确定，所以选择list。
2、终止条件：当访问的节点为空时，return
3、递归函数的逻辑：先访问一个节点，递归访问其他节点
144.二叉树的前序遍历
代码如下：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result=new ArrayList<>();
preorder(root,result);
return result;
}
public void preorder(TreeNode root,List<Integer> result){
if(root==null) return;
result.add(root.val);
preorder(root.left,result);
preorder(root.right,result);
}
}
145.二叉树的后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result=new ArrayList<>();
postOrder(root,result);
return result;
}
public void postOrder(TreeNode root,List result){
if(root==null) return;
postOrder(root.left,result);
postOrder(root.right,result);
result.add(root.val);
}
}
94.二叉树的中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result=new ArrayList<>();
inOrder(root,result);
return result;
}
public void inOrder(TreeNode root,List result){
if(root==null) return;
inOrder(root.left,result);
result.add(root.val);
inOrder(root.right,result);
}
}
迭代遍历
先序遍历
思路：由于先序遍历是中左右，现将根节点入栈。设置循环判断栈是否为空。弹出根节点并记录val，依次判断右节点和左节点是否为空，不为空则入栈。这样第二次循环就会先弹出左节点，对左节点进行记录和进一步判断。
即先序遍历顺序：中-左-右；入栈顺序中-右-左
代码如下：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result=new ArrayList<>();
if(root==null){
return result;
}
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur=stack.pop();
result.add(cur.val);
if(cur.right!=null){
stack.push(cur.right);
}
if(cur.left!=null){
stack.push(cur.left);
}
}
return result;
}
}
中序遍历
思路：由于中序遍历是左中右，所以需要不断的查找左节点。先建立一个指针指向根节点，判断指针或栈不为空时进入循环，当当前指针不为空时，将指针节点入栈，并使指针指向该节点的左节点，当当前节点为空但栈不为空时，弹出栈头节点并记录val，将右节点入栈。重复循环。
代码如下：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result=new ArrayList<>();
if(root==null) return result;
Stack<TreeNode> stack=new Stack<>();
TreeNode node=root;
while(node!=null || !stack.isEmpty()){
if(node!=null){
stack.push(node);
node=node.left;
}else{
node=stack.pop();
result.add(node.val);
node=node.right;
}
}
return result;
}
}
后序遍历
思路：先序遍历得到的结果是中左右，只需修改先序遍历代码得到中右左，再将结果反转即为后序遍历想要的结果。
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result=new ArrayList<>();
if(root==null){
return result;
}
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur=stack.pop();
result.add(cur.val);
if(cur.left!=null){
stack.push(cur.left);
}
if(cur.right!=null){
stack.push(cur.right);
}
}
Collections.reverse(result);
return result;
}
}
如果直接进行后序遍历，会比较麻烦。
第一步需要先见一个指针和循环将左节点全部入栈，之后弹出栈顶元素，判断栈顶元素的右孩子是否为空或者之前已经访问过（这里需要建立一个指针pre记录之前处理过的右孩子），如果成立则记录该节点，并将该节点记为pre，令node为null；否则需要将该节点重新放回栈中，并将指针指向他的右孩子。
代码如下：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result=new ArrayList<>();
if(root==null){
return result;
}
Stack<TreeNode> stack=new Stack<>();
TreeNode node=root;
TreeNode pre=null;
while(node!=null || !stack.isEmpty()){
while(node!=null){
stack.push(node);
node=node.left;
}
node=stack.pop();
if(node.right==null || node.right==pre){
result.add(node.val);
pre=node;
node=null;
}else{
stack.push(node);
node=node.right;
}
}
return result;
}
}
统一迭代
思路：采用标记法对在将节点入栈时对需要处理的节点进行标记，即在处理的节点放入栈之后，紧接着放入一个空指针作为标记。
每种遍历都在中间节点的后面放入null，但是由于遍历顺序不同，所以存入中间节点的顺序也不同。先序遍历希望得到的结果是中左右，所以入栈顺序是右左中null；中序遍历希望得到的结果是左中右，所以入栈顺序是右中null左；后序遍历希望得到的结果是左右中，所以入栈顺序是中null右左。
代码如下
先序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result=new ArrayList<>();
if(root==null) return result;
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node=stack.pop();
if(node!=null){
//先放右节点
if(node.right!=null) stack.push(node.right);
if(node.left!=null) stack.push(node.left);
//最后放中间节点
stack.push(node);
//存入null
stack.push(null);
}else{
node=stack.pop();
result.add(node.val);
}
}
return result;
}
}
中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result=new ArrayList<>();
if(root==null) return result;
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node=stack.pop();
if(node!=null){
//先放右节点
if(node.right!=null) stack.push(node.right);
//再放中间节点
stack.push(node);
//存入null
stack.push(null);
//最后放左节点
if(node.left!=null) stack.push(node.left);
}else{
node=stack.pop();
result.add(node.val);
}
}
return result;
}
}
后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result=new ArrayList<>();
if(root==null) return result;
Stack<TreeNode> stack=new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node=stack.pop();
if(node!=null){
//先放中间节点
stack.push(node);
//存入null
stack.push(null);
//再放右节点
if(node.right!=null) stack.push(node.right);
//最后放左节点
if(node.left!=null) stack.push(node.left);
}else{
node=stack.pop();
result.add(node.val);
}
}
return result;
}
}
层序遍历
思路：借助队列先进先出，一层层遍历。可以通过队列的长度来判断某一层是否遍历完成，每次pull长度减一。掌握队列方法，代码实现就比较简单了
102.二叉树的层序遍历
代码如下：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result=new ArrayList<>();
if(root==null) return result;
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int len=queue.size();
List<Integer> levelResult=new ArrayList<>();
while(len>0){
TreeNode node=queue.poll();
levelResult.add(node.val);
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
len--;
}
result.add(levelResult);
}
return result;
}
}
递归方法思路：1、终止条件：节点为null时返回；2、传入的参数：一个记录深度的变量deep，每次调用递归函数时传入节点、deep和result；3、递归函数逻辑：每次调用deep深度加一，当result列表中的元素值小于deep时新建一个每层的list列表添加到result列表。获取result列表中下标为当前层数-1的list列表加入当前节点的val。分别对该节点的左右孩子调用递归函数。
代码如下：
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result=new ArrayList<>();
lOrder(root,0,result);
return result;
}
public void lOrder(TreeNode root,int deep,List<List<Integer>> result){
if(root==null) return;
deep++;
while(result.size()<deep){
List<Integer> levelResult=new ArrayList<>();
result.add(levelResult);
}
result.get(deep-1).add(root.val);
lOrder(root.left,deep,result);
lOrder(root.right,deep,result);
}
}
层序遍历还有一些题，可能会在之后另出帖子一起写。。。
标签：node,遍历,迭代,List,二叉树,null,root,stack,result From： https://blog.csdn.net/m0_51007517/article/details/142136177