二叉树-非递归遍历

1 先序遍历

具体过程：

首先申请一个新的栈，记为stack。
然后将头节点head压入stack。
每次从stack中弹出栈顶结点，记为cur，然后打印cur结点的值。如果cur右孩子不为空的话，将cur的右孩子先压入stack中。最后如果cur的左孩子不为空的话，将cur的左孩子压入stack中。
不断重复步骤3，直到stack为空，全部过程结束。

二叉树-非递归遍历

示例代码（Java）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root==null){
            return new ArrayList<Integer>();
        }
        ArrayList<Integer>res=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<TreeNode>();
        stack.push(root);
        TreeNode cur=null;
        while(!stack.isEmpty()){
            cur=stack.pop();
            res.add(cur.val);
            if(cur.right!=null){
                stack.push(cur.right);
            }
            if(cur.left!=null){
                stack.push(cur.left);
            }
        }
        return res;
    }
}

2 中序遍历

具体过程：

申请一个新的栈记为stack，申请一个变量cur，初始值令cur等于头结点。
先把cur结点压入栈中，对以cur结点为头的整棵子树来说，依次把整棵树的左边界压入栈中，即不断令cur=cur.left，然后重复步骤2。
不断重复步骤2，直到发现cur为空，此时从stack中弹出一个结点，记为node。打印node的值，并让cur=node.right，然后继续重复步骤2。
当stack为空并且cur为空时，整个过程结束。

示例代码（Java）

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root==null){
            return new ArrayList<Integer>();
        }
        ArrayList<Integer> res=new ArrayList<Integer>();
        Stack<TreeNode> s=new Stack<>();
        TreeNode cur=root;//判断是否叶节点指针
        while(cur!=null||!s.isEmpty()){
            if(cur!=null){//非叶子结点
                s.push(cur);
                cur=cur.left;
            }else{
                cur=s.pop();
                res.add(cur.val);
                cur=cur.right;
            }
        }
        return res;
    }
}

3 后序遍历

方法一：使用两个栈实现

申请一个栈，记为s1，然后将头结点压入s1。
从s1中弹出的结点记为cur,然后先把cur的左孩子压入s1中，然后把cur的右孩子压入s1中。
在整个过程中，每一个从s1中弹出的结点都放进第二个栈s2中。
不断重复步骤2和步骤3，直到s1为空，过程停止。
从s2中一次弹出结点并打印，打印的顺序就是后序遍历的顺序了。

示例代码（Java）

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root==null){
            return new ArrayList<Integer>();
        }
        ArrayList<Integer>res=new ArrayList<>();
        Stack<TreeNode> s1=new Stack<TreeNode>();
        Stack<TreeNode> s2=new Stack<TreeNode>();
        s1.push(root);
        TreeNode cur=null;//当前的栈顶节点
        while(!s1.isEmpty()){
            cur=s1.pop();
            s2.push(cur);
            if(cur.left!=null){
                s1.push(cur.left);
            }
            if(cur.right!=null){
                s1.push(cur.right);
            }
        }
        while (!s2.isEmpty()){
            res.add(s2.pop().val);
        }
        return res;
    }
}

方法二：使用一个栈实现

申请一个栈，记为stack，将头结点压入stack，同时设置两个变量h和c。在整个流程中，h代表最近一次弹出并打印的结点，c代表当前stack的栈顶结点，初始时令h为头结点，c为null。
每次令c等于当前stack的栈顶结点，但是不从stack中弹出结点。此时分以下三中情况：
（1）如果c的左孩子不为空，并且h不等于c的左孩子，也不等于c的右孩子，则把c的左孩子压入stack中。
（2）如果情况1不成立，并且c的右孩子不为空，并且h不等于c的右孩子，则把c的右孩子压入stack中。
（3）如果情况1和情况2都不成立，那么从stack中弹出c并打印，然后令h等于c。

示例代码（Java）

public void postOrder(ArrayList<Integer>arr,TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<TreeNode>();
        stack.push(root);
        TreeNode temp=null;//最近一次弹出并打印的节点
        TreeNode cur=root;//当前的栈顶节点
        while(!stack.isEmpty()){
            cur=stack.peek();
            if(cur.left!=null&&temp!=cur.left&&temp!=cur.right){
                stack.push(cur.left);
            }else if(cur.right!=null&&temp!=cur.right){
                stack.push(cur.right);
            }else {
                temp=stack.pop();
                arr.add(temp.val);
            }
        }
    }

二叉树-非递归遍历

1 先序遍历

2 中序遍历

3 后序遍历

方法一：使用两个栈实现

方法二：使用一个栈实现

相关推荐