深度优先遍历DFS 非递归算法理解与Java实现(树状结构非数组输入)

给出一个类TreeNode，如何对其进行非递归的DFS进行遍历？

非递归进行图的遍历会用到两种数据结构，栈与队列。考虑到两种数据结构的特性，不难想出栈更适合深度优先遍历，队列更适合广度优先遍历。

针对深度优先遍历算法这里不多加赘述了，总结起来DFS就是一条路走完再到最近的保存点走另外一条，BFS是每次遇到岔路口都往前看看，每个路都往前探探。

在DFS中，首先要探一个方向的路，当前假设先左后右，因此就是一直找节点的左孩子，直到左侧的节点为空（无左孩子）时，再往右侧走。每遇到一个新节点都要先左后右的进行遍历。针对非递归，它的难点主要是树的入栈和出栈。在树结构为数组时，我们可以用一个visited数组来保存该节点是否已经遍历过，以及已访问的子孩子数与该节点的子孩子数是否相同。但当树结构为链表时，做标记位没有那么方便的对应上了。

（这段看不懂直接看代码吧，我描述得不是很清楚）入栈和出栈的主要思路是在遍历到当前节点时，会判断它有没有孩子节点，有的时候将其孩子节点入栈。在开始访问了它右孩子节点（开始访问指的是判断右孩子是否存在之前）将其出栈。遍历终止的条件就是看栈内有无元素，栈内元素表示该节点的左右孩子或右孩子还没访问。值得注意的是，存进栈内的元素一定会先访问左孩子，如果左孩子存在则继续存，如果左孩子不存在就会访问右孩子。所以在这里我加了一个判断位，”左侧是否已访问(isleft)“。若左侧已访问完成则访问右侧， 左侧未访问就访问左侧。若push进去的元素，isleft设为false。若pop出来的元素，isleft设为true（由于程序流程设计，已经在pop阶段一定是左孩子已访问）。**为什么要在开始判断右孩子是否存在之前就要让该节点pop出去？**因为栈内节点都是左侧访问完了的，我们会获取的是他的右侧节点，右侧访问完他就没用了，如果用传统做法访问完右孩子再pop父节点则分不出它有没有访问过了。

import java.util.*;
import java.util.Stack;
import java.util.ArrayList;



public class Solution {
    
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        Stack st1 = new Stack();
        int isLeft=0;
        st1.push(t1);
        System.out.println(t1.val);
        while (st1.size()!=0){
            TreeNode pointer=st1.peek();
            if(isLeft==0){
                if(pointer.left!=null){
                    System.out.println(pointer.left.val);
                    st1.push(pointer.left);
                    isLeft=0;
                }else
                    isLeft=1;
            }
            else{
                st1.pop();
                isLeft=1;
                if(pointer.right!=null){
                    System.out.println(pointer.right.val);
                    st1.push(pointer.right);
                    isLeft=0;
                }
            }
        }
        return t1;
    }
}

我知道我这篇文章写的不清晰。写这个的初衷是在网上搜DFS的非递归方法，得到的都是假的dfs，即遍历节点时直接将左右孩子一起进栈而非先左后右。看到这篇文章感觉不清晰的朋友可以跟我在评论区沟通。希望我有一天能真正讲懂技术这东西。