树的一些经典 Oj题讲解_代码007(未授权)

本文介绍: 树的OJ题讲解

我们知道树的遍历有前序遍历中序遍历后序遍历然后我们如果用递归的方式去解决，对我们来说应该是轻而易举的吧！那我们今天要讲用迭代（非递归）实现树的相关遍历
首先呢我们得知道迭代解法本质上也是在模拟递归，因为递归的过程中使用了系统栈，所以我们在迭代的时候也要用Stack来模拟系统栈。
我们要一开始就要创建一个顺序表接收打印的值最终程序结束输出出来。
首先我们要创建一个栈来存放结点，首先我们就要打印根节点的值，此时栈中的内容为null，所以我们优先将头结点puth进去栈，然后打印。其实就很好理解如果树为空直接就返回了。

在这里插入图片描述
我们首先从根节点开始遍历只要节点不为空就进入循环就push 进栈再打印再去遍历左子树，直到左子树为空，就进不来循环了我们就要从栈中弹出元素，去遍历他的右子树但是现在只有一层循环不能够继续进入回到上面再进入左子树的循环那怎么办呢我们就可以再加一层循环在最外面包着他们判断条件依然是节点不为空，但是这样就解决了吗当然还没有你去遍历右子树肯定会最后右孩子结点为空又怎么返回循环呢此时已经节点为空了进不去循环了但是还没遍历结束，该怎么办呢现在栈还没空也是一个判断条件我们就可以再外层循环加一个条件栈不为空。

最终的实现你们可以参考代码：

public List<Integer> preorderTraversal(TreeNode root) {
        //先定义一个顺序表去接收
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }

        //用链表去实现一个栈
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
        while(cur != null){
            list.add(cur.val);
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        cur = cur.right;
        }
        return list;
    }

根据代码去分析上面那棵二叉树我们就可以输出他的二叉树遍历序列。

通过上面的先序遍历，我们可以知道大概的思路。其实中序遍历迭代（非递归）实现和先序遍历的实现其实差不太多就输出的位置换一下因为是 左根右 ，所以我们先去遍历完左子树，push进栈。左子树为空的时候再从栈中弹出元素打印元素。
具体代码实现如下：

 public List<Integer> inorderTraversal(TreeNode root) {
 //先定义一个顺序表去接收
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }

        //用链表去实现一个栈
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
        while(cur != null){
            
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        list.add(cur.val);
        cur = cur.right;
        }
        return list;
    }

写到这里大家是不是觉得 so easy 后序遍历想直接开敲，但是这里提醒大家后序遍历没有前序和中序那样简单了后序会涉及到一个记录结点。下面我们来分析一下

 public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        //创建一个栈
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;//用来记录打印过的结点
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            //只能拿出来看一下 不能弹出来
            TreeNode top = stack.peek();
            if(top.right == null ||top.right == prev ){ 
    //这里代码会出现死循环  因为会一直在那个结点 所以我们要记录的节点 加一个判断条件
                stack.pop();
                list.add(top.val);
                prev = top;
            }else{
                cur = top.right;
            }
        }
        return list;
    }

 StringBuilder sb = new StringBuilder();
    public String tree2str(TreeNode root) {
        preoderTraveral(root);
        return sb.toString();
    }
    private void preoderTraveral(TreeNode root){
        if(root == null){
            return;
        }
        sb.append(root.val);
        if(root.left != null || root.right != null){
            sb.append("(");
            preoderTraveral(root.left);
            sb.append(")");
            if(root.right != null){
                sb.append("(");
                preoderTraveral(root.right);
                sb.append(")");
            }
        }
    }