16.二叉树的前序、中序、后序遍历

题目描述：

给定一个二叉树的根节点root,返回它的前序、中序、后序遍历。

解题思路：

在做这个题目之前，打开了LeetCode树与二叉树的专项训练这一节，回顾复习了二叉树的几种遍历，以及使用栈来代替递归，遍历二叉树的方法，基本上都是靠题解完成的。

对于前序遍历、中序遍历、后序遍历都有三种解法，递归、迭代、Morris遍历。对于Morris遍历，还没有细看，只是先熟悉了迭代和递归这两种解法。

递归其实就是访问根节点的顺序的不同

前序遍历：根节点、左子树、右子树

中序遍历：左子树、根节点、右子树

后序遍历：左子树、右子树、根节点

迭代就是利用栈的性质，模拟递归栈的过程

一般都有一个模板解法，即遍历到最左节点，前序遍历是在遍历的同时，将节点值加入数组；中序遍历则是在遍历完最左节点后，先将最左节点加入数组，然后弹出加入根节点；后序遍历则是利用和先序遍历的逆操作，找到最右节点...

对于前序和后序遍历，还有一种是利用栈先进后出的方式，前序遍历：根-->左-->右，那么入栈顺序就可以是根-->右-->左；后续遍历：左-->右-->根，入栈顺序就是根-->左-->右，出栈顺序就是根-->右-->左，那么倒序就是左右根了。

Morris遍历，其实就是利用节点的空指针，来优化空间的一种解法，把多余的空指针，变成是否完成遍历的标志。其思想大致是找到根节点的前驱结点，让前驱结点的空指针指向根节点，完成这样一个连接的过程。原本是null的值，如今变成了后续的根节点，就说明该节点已经访问过了。

对于前序遍历来说：根左右的遍历方式，建议先看中序遍历的Morris，然后看了之后，其实前序遍历就是在中序遍历Morris的基础上，在标识的同时，进行先根遍历，因为前序遍历和中序遍历，都是先左子树再右子树的，只不过前序遍历是在标识前驱结点pre的同时，就进行了访问，而中序遍历是先标识，等到中序遍历到了该节点，再进行访问。

对于中序遍历来说：左根右的遍历方式，可以知道根节点的前驱结点，是左子树的最右节点，因此：

如果左子树为空，访问根节点，然后遍历右子树

如果左子树不为空，找到左子树的最右节点，也就是当前根节点的前驱结点

如果前驱结点的右子树为空，说明需要加上这样一条连接线pre.right = root表示将前驱结点和根节点连接标识

如果前驱结点的右子树不为空，那么右子树一定是之前加的连接线，也就是说pre.right == root,表示此时root的左子树已经访问完毕了，下一个需要访问的就是根节点了。访问

对于后序遍历，这个方法比较复杂，在标识之后，进行访问的时候，需要倒序加入上一层单链表的值，这个单链表，是当前节点一直.right得到的单链表，在断开标识这条线之后，通过遍历.right，就可以得到一个无环的单链表。

代码：

递归：

//前序遍历
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List preorderTraversal(TreeNode root) {
        List res = new ArrayList();
        preorder(root, res);
        return res;

    }

    public void preorder(TreeNode root, List res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }

}

//中序遍历
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List inorderTraversal(TreeNode root) {
        List res = new ArrayList();
        inorder(root, res);
        return res;
    }
    public void inorder(TreeNode root, List res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);

    }
}

//后序遍历
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List postorderTraversal(TreeNode root) {
        List res = new ArrayList();
        postor(root, res);
        return res;
    }

    public void postor(TreeNode root, List res) {
        if (root == null) {
            return;
        }
        postor(root.left, res);
        postor(root.right, res);
        res.add(root.val);
    }
}

模板法：

//前序遍历
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List preorderTraversal(TreeNode root) {
        Deque stack = new LinkedList();
        List res = new ArrayList();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                res.add(node.val);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return res;
    }

}

//中序遍历
//中序遍历
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List inorderTraversal(TreeNode root) {
        Deque stack = new LinkedList();
        List res = new ArrayList();
        TreeNode node = root;
        
        
        while (!stack.isEmpty() || node != null){
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            res.add(node.val);
            node = node.right;
            
        }
        return res;

    }
}

//后序遍历
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //模板解法，先遍历到树的右子树的最右节点，根右左--》反转就是左右根
    public List postorderTraversal(TreeNode root) {
        List res = new ArrayList();
        Deque stack = new LinkedList();
        Deque stackRevRes = new LinkedList();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stackRevRes.push(node.val);
                stack.push(node);
                node = node.right;
            }
            node = stack.pop();
            node = node.left;
        }
        while (!stackRevRes.isEmpty()) {
            res.add(stackRevRes.pop());
        }
        return res;
        
    }
}

栈的性质：

//前序遍历
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //利用栈的性质，根左右，可以先让右节点入栈，然后让左节点入栈，这样出栈顺序就是先左后右了
    public List preorderTraversal(TreeNode root) {
        Deque stack = new LinkedList();
        List res = new ArrayList();
        TreeNode node = root;
        if (root == null) {
            return res;
        }
        stack.push(node);
        while (!stack.isEmpty()) {
            node = stack.pop();
            res.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return res;
    }

}

//后序遍历
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //利用栈的性质，由于后序遍历是左右根，因此利用栈根左右入栈，这样出栈的时候就是根右左，然后将其反转，就是后序遍历了。后序遍历和前序遍历的区别就是根节点、左右子树谁先谁后，并且二者左子树都是先于右子树的，所以不是简单的前序遍历的反转。
    public List postorderTraversal(TreeNode root) {
        List res = new ArrayList();
        Deque stack = new LinkedList();
        Deque stackRevRes = new LinkedList();
        TreeNode node = null;
        if (root == null) {
            return res;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            node = stack.pop();
            stackRevRes.push(node.val);
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        while (!stackRevRes.isEmpty()) {
            res.add(stackRevRes.pop());
        }
        return res;
        
    }
}

后续遍历，不使用倒序数组的迭代，使用prev指针

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //利用prev指针标识，当前从栈中退出的节点是什么
    public List postorderTraversal(TreeNode root) {
        List res = new ArrayList();
        Deque stack = new LinkedList();
        TreeNode prev = null;
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            
            node = stack.pop();//先将当前节点出栈，判断是否已经左右子树已经访问，如果刚刚从栈中退出的prev节点是其右节点，说明轮到此节点出栈；如果不是，需要将此节点再次压栈，遍历其右节点
            if (node.right == null || node.right == prev) {
                res.add(node.val);
                prev = node;
                node = null;//因为刚刚这个节点，已经是最左的节点了，因此下一次需要继续出栈，把node=null即可
            } else {
                stack.push(node);
                node = node.right;
            }

            
        }
        
        return res;
        
    }
}

Morris遍历

//前序遍历
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //Morris遍历，其实和中序的差不多，只不过，在中序遍历中，可以看做是先标记中序遍历中的前驱结点（也就是左子树的最右节点），然后等遍历到的时候，再访问；对于前序遍历，可以看做是在标记前驱结点的同时，已经访问了当前节点。
    public List preorderTraversal(TreeNode root) {
        TreeNode node = root;
        TreeNode pre = null;
        List res = new ArrayList<>();
        if (node == null) {
            return res;
        }
        while (node != null) {
            if (node.left != null) {
                
                pre = node.left;
                while (pre.right != null && pre.right != node) {
                    pre = pre.right;
                }
                if (pre.right == null) {
                    pre.right = node;
                    res.add(node.val);//在标记时，就开始访问该节点
                    node = node.left;
                    
                }else {
                    pre.right = null;
                    node = node.right;
                }
            }else {
                res.add(node.val);
                node = node.right;
                
            }
        }
        return res;
    }

}

//中序遍历
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List inorderTraversal(TreeNode root) {
        List res = new ArrayList();
        TreeNode pre = null;
        if (root == null) {
            return res;
        }
        while (root != null) {
            if (root.left == null) {
                res.add(root.val);
                root = root.right;
            } else {
                pre = root.left;
                while (pre.right != null && pre.right != root) {
                    pre = pre.right;
                } 
                if (pre.right == null) {
                    pre.right = root;
                    root = root.left;
                }else {
                    res.add(root.val);
                    pre.right = null;//这里的断开连接，只是为了恢复二叉树的原始结构。
                    root = root.right;
                }
            }
        }
        return res;

    }
}

//后序遍历
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    public List postorderTraversal(TreeNode root) {
        List res = new ArrayList();
        Deque resStack = new LinkedList<>();
        if (root == null) {
            return res;
        }
        TreeNode cur1 = root;//遍历当前树
        TreeNode pre = null;//当前树的最右节点
        while (cur1 != null) {
            pre = cur1.left;
            if (pre == null) {
                cur1 = cur1.right;

            }else {
                while (pre.right != null && pre.right != cur1) {
                    pre = pre.right;
                }
                if (pre.right == null) {
                    pre.right = cur1;
                    cur1 = cur1.left;
                    
                } else {
                    pre.right = null;//断开连接，在断开连接之后，进行下一步
                    postMorriosVisit(cur1.left, resStack, res);//将当前节点的左子树倒序加入到数组中，通过遍历节点的右节点，因为已经断开了连接，是一个无环单链表
                    cur1 = cur1.right;
                }
            }
        }
        postMorriosVisit(root, resStack, res);
        
        return res;

            
    
        
        
        
    }

    public void postMorriosVisit(TreeNode root, Deque resStack, List res) {
        while (root != null) {
            resStack.push(root.val);
            root = root.right;
        }
        while (!resStack.isEmpty()) {
            res.add(resStack.pop());
        }
    }
}

递归一刷LeetCode 栈迭代 Morris遍历二叉树

16.二叉树的前序、中序、后序遍历

递归：

模板法：

栈的性质：

后续遍历，不使用倒序数组的迭代，使用prev指针

Morris遍历

相关

数据结构--栈（C语言实现）

Linux获取栈空间大小

fibnacci数列递归实现

执行上下文与执行上下文栈：变量声明提升与函数声明提升执行上下文执行上下文栈测试

二叉树的存储结构

Python栈溢出——设置python栈大小

[C#] 使用递归将多条路径生成树

Python 之父的解析器系列之五：左递归 PEG 语法

关于SQL递归查询在不同数据库中的实现方法

Python入门--13--递归

0106-105-从中序与后序遍历序列中构造二叉树

map文件堆栈大小

标签