二叉树的非递归遍历

二叉树的前序非递归遍历

/**
 * 先根遍历迭代法
 */
public List<Integer> preOrderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root == null) return list;
    Stack<TreeNode> stack = new Stack<>();

    stack.push(root);
    TreeNode curNode;
    while(!stack.isEmpty()) {

        curNode = stack.pop();
        list.add(curNode.value);

        if(curNode.right != null) {
            stack.push(curNode.right);
        }
        if(curNode.left != null) {
            stack.push(curNode.left);
        }
    }
    return list;
}

中序优先非递归遍历

public List<Integer> inOrderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curNode = root;
        while(!stack.isEmpty() || curNode != null) {
            while(curNode != null) {
                stack.push(curNode);
                curNode = curNode.left;
            }

            if(!stack.isEmpty()) {
                curNode = stack.pop();
                list.add(curNode.value);
                curNode = curNode.right;
            }
        }
        return list;
    }

后序优先非递归遍历（双栈）

/**
 * 参考：https://segmentfault.com/a/1190000016674584?utm_medium=referral&utm_source=tuicool
 * 仔细观察一下后序遍历的顺序：左 -- 右 -- 根
 * 根节点在最后，对照先序遍历的顺序：根 -- 左 -- 右
 * 这里我们可以想到，将先序遍历微调为：根 -- 右 -- 左的顺序，这个微调很简单，只是在push节点到栈
 * 里时，先push左节点，再push右节点，此时栈顶是右节点，那么下次循环就会先弹出右节点，此时，
 * 再把弹出的右节点push到反向栈 stackReverse 里即可。
 * 核心：我们只需要增加一个栈来反向输出微调之后的先序遍历的每个节点，就可以得到后序遍历顺序。
 */
public List<Integer> postOrderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if (root == null) return list;
    Stack<TreeNode> stack = new Stack<>();
    Stack<TreeNode> stackReverse = new Stack<>();

    stack.push(root);
    TreeNode curNode;
    while (!stack.isEmpty()) {
        curNode = stack.pop();
        stackReverse.push(curNode);

        if (curNode.left != null) {
            stack.push(curNode.left);
        }
        if(curNode.right != null) {
            stack.push(curNode.right);
        }
    }

    while(!stackReverse.isEmpty()) {
        curNode = stackReverse.pop();
        list.add(curNode.value);
    }
    return list;
 }

后序优先非递归遍历

/**
 * 双向队列法和先序遍历迭代的区别只是使用了 Deque 这种链表数据结构，每次都
 * 从链表头插入新节点。由于 LinkedList 本身已经实现了 Deque 接口和List接口，因此
 * LinkedList 可以作为一个双向队列来使用，同时本身也是List的实现类。可以很方便地
 * 实现将新节点插入到表头的需求。
 */
 public List<Integer> postOrderTraversalByDeque(TreeNode root) {
     LinkedList<Integer> resultList = new LinkedList<>();
     if (root == null) return resultList;
     Stack<TreeNode> stack = new Stack<>();
     stack.push(root);
     TreeNode curNode;

     while(!stack.isEmpty()) {
         curNode = stack.pop();
         resultList.addFirst(curNode.value);//这里从前往后添加

         if (curNode.left != null) {
             stack.push(curNode.left);
         }
         if (curNode.right != null) {
             stack.push(curNode.right);
         }
     }
     return resultList;
 }

参考文献

BenYoung : 二叉树遍历Java(递归+迭代)：前序、中序和后续遍历（双栈法+Deque法）

赏

谢谢你请我吃糖果

微信