有意思的利用栈实现二叉树的三种遍历

Posted on |

二叉树的preorder,inorder,postorder三种遍历方式，通过递归都能比较优雅的实现，但是递归可能会遇到递归栈过深的情况，如果考虑到这些情况，可以用stack栈替代递归的方案，这里列举三种遍历方式用递归替代的方案，个人认为比较巧妙。

preorder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<Integer> preorderTraversal(TreeNode root) {
        //step1 栈保存右节点
        Stack<TreeNode> stack=new Stack<>();
        List<Integer> result= new ArrayList<>();
        if (root!=null) {
            stack.push(root);
        }
        //循环迭代
        while (!stack.isEmpty()){
            TreeNode current=stack.pop();
            result.add(current.val);
            //将先输出的节点放到栈顶 bread-first-search是直接按照从左到右的顺序（利用队列） 这里是利用stack特点将左子树遍历完（利用栈）
            if (current.right!=null) {
                stack.push(current.right);
            }
            if (current.left!=null) {
                stack.push(current.left);
            }
        }
        return result;
    }

inorder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        if (root==null) return res;

        Stack<TreeNode> stack=new Stack<>();
        TreeNode curr=root;

        while(curr!=null || !stack.isEmpty()){
            while (curr!=null){
                stack.push(curr);
                curr=curr.left;
            }
            curr=stack.pop();
            res.add(curr.val);
            curr=curr.right;
        }
        return res;
    }

postorder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> postorderTraversal(TreeNode root) {
     List<Integer> list = new ArrayList<>();
     if(root == null) return list;
     Stack<TreeNode> stack = new Stack<>();
     stack.push(root);
     while(!stack.isEmpty()) {
         TreeNode curr = stack.pop();
         list.add(0,curr.val);
         if(curr.left!=null) {
             stack.push(curr.left);
         }
         if(curr.right!=null) {
             stack.push(curr.right);
         }
     }
     return list;
 }