二叉树的遍历问题

发表于 | 分类于 | 阅读次数

Description

leetcode上的144,145，like this:Recursive solution is trivial, could you do it iteratively?
使用非递归的方法实现前，中，后序遍历，包括一些使用该思想的题目
这里就将前序遍历，中序遍历，后续遍历，层次遍历全部都写一遍吧，当做是总结，后期如果遇到二叉树遍历的题目，也会总结到此处，长期更新

前序遍历

前序遍历的递归思想非常简单，一般问题无非就是在数据结构书中给出的算法的print上做文章.

1
2
3
4
5
6
7
public void preorderTraversal(List<Integer> list,TreeNode node) {
    if(node!=null){
        list.add(node.val);
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }
}

非递归思想也比较简单，只要知道用栈来存储就可以了，因为要先输出左子树，后输出右子树，由栈的特点需要先存储右子树，后存储左子树.

1
2
3
4
5
6
7
8
9
10
11
12
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list=new ArrayList<>();
    Stack<TreeNode> stack=new Stack<>();
    if(root!=null)stack.push(root);
    while (!stack.isEmpty()){
        TreeNode node=stack.pop();
        list.add(node.val);
        if(node.right!=null)stack.push(node.right);
        if(node.left!=null)stack.push(node.left);
    }
    return list;
}

中序遍历

中序遍历的递归实现只是将前序遍历的print下移即可

1
2
3
4
5
6
7
public void orderTraversal(List<Integer> list,TreeNode node) {
    if(node!=null){
        orderTraversal(node.left);
        list.add(node.val);
        orderTraversal(node.right);
    }
}

非递归思想就是对于一个节点，先遍历左子树，直到其左子树为空，出栈，其中出栈的元素只能指向其右子树，继续重复上述过程；非要自己造，结果写了一二十分钟也没写出来。
参考：二叉树的非递归遍历
海子写的文章确实很好，若是有时间就好好读读了

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

后序遍历

递归方法如下

1
2
3
4
5
6
7
public void postorderTraversal(List<Integer> list,TreeNode node) {
    if(node!=null){
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        list.add(node.val);
    }
}

非递归思想：对于栈顶节点，如果其左子树和右子树都为空或者是其左子树和右子树都已经遍历过了，就输出该节点，否则依次将右节点，左节点入栈，这个顺序和之前前序遍历是一样的，这里主要是用一个列表记录该节点是否已近被访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list=new ArrayList<>();
    Stack<TreeNode> stack=new Stack<>();
    List<TreeNode> isTraversal=new ArrayList<>();
    TreeNode node=root;
    if(root!=null)stack.push(root);
    isTraversal.add(null);//目的是为了下面的if语句中的判断，如果只有一个孩子的情况
    while (!stack.isEmpty()){
        node=stack.peek();
        if((node.left==null&&node.right==null)||(isTraversal.contains(node.left)&&isTraversal.contains(node.right))){
            list.add(node.val);
            stack.pop();
        }else{
            if(node.right!=null){
                stack.push(node.right);
                isTraversal.add(node.right);
            }
            if(node.left!=null){
                stack.push(node.left);
                isTraversal.add(node.left);
            }
        }
    }
    return list;
}

层次遍历

层次遍历的思想经典的方法是用队列来实现，当然比较好的方法是直接用递归，有很多层次遍历的题目都是使用递归解决的，节省了队列的开销。这里从最基础的栈到使用递归来描述层次遍历。

[leetcode 102] Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree[3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its level order traversal as:

1
2
3
4
5
[
  [3],
  [9,20],
  [15,7]
]

举这道题只是为了熟悉层次遍历的基本实现方法，当然了基础的层次遍历只是按层打印节点的值，而不需要分层，用一个队列就可以了，这里就不罗列了；此题要求每层输出一个list，就要用两个队列，以区分层，此为最最普通的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public List<List<Integer>> levelOrder(TreeNode root) {
    Queue<TreeNode> queue1=new LinkedList<>();
    Queue<TreeNode> queue2=new LinkedList<>();
    List<List<Integer>>lists=new ArrayList<>();
    if(root==null)return lists;
    queue1.offer(root);
    while (!queue1.isEmpty()||!queue2.isEmpty()){
        List<Integer>list=new ArrayList<>();
        if(!queue1.isEmpty()){
            while (!queue1.isEmpty()){
                TreeNode temp=queue1.poll();
                list.add(temp.val);
                if(temp.left!=null)queue2.offer(temp.left);
                if(temp.right!=null)queue2.offer(temp.right);
            }
        }else {
            while (!queue2.isEmpty()){
                TreeNode temp=queue2.poll();
                list.add(temp.val);
                if(temp.left!=null)queue1.offer(temp.left);
                if(temp.right!=null)queue1.offer(temp.right);
            }
        }
        lists.add(list);
    }
    return lists;
}

[leetcode 103] Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its zigzag level order traversal as:

1
2
3
4
5
[
  [3],
  [20,9],
  [15,7]
]

这道题和上题的区别在于偶数行要逆序，如果用队列的话有一个反转的过程，用栈就会方便很多，前一个栈元素从左到右入栈，后一个栈元素从右到左入栈，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    Stack<TreeNode> reStack=new Stack<>();
    Stack<TreeNode> stack=new Stack<>();
    List<List<Integer>>lists=new ArrayList<>();
    if(root==null)return lists;
    reStack.push(root);
    while (!reStack.isEmpty()||!stack.isEmpty()){
        List<Integer>list=new ArrayList<>();
        if(!reStack.isEmpty()){
            while (!reStack.isEmpty()){
                TreeNode temp=reStack.pop();
                list.add(temp.val);
                if(temp.left!=null)stack.push(temp.left);
                if(temp.right!=null)stack.push(temp.right);
            }
        }else {
            while (!stack.isEmpty()){
                TreeNode temp=stack.pop();
                list.add(temp.val);
                if(temp.right!=null)reStack.push(temp.right);
                if(temp.left!=null)reStack.push(temp.left);
            }
        }
        lists.add(list);
    }
    return lists;
}

当然前面讲到过，这样的方法开销大，是可以用递归解决的，当该层没有list的时候就创建list，如果该层为奇数层就在list的0位添加(即逆序)，否则正序添加，每个节点都有相应的层标号，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    helper(root, 0, res);
    return res;
}
public void helper(TreeNode node, int level, List<List<Integer>> res){
    if(node == null) return;
    if(res.size() <= level)
            res.add(level, new LinkedList<Integer>());
    if(level%2 == 0)    res.get(level).add(node.val);
    else                res.get(level).add(0,node.val);
    helper(node.left, level+1, res);
    helper(node.right, level+1, res);
}

[leetcode 107] Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree[3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its bottom-up level order traversal as:

1
2
3
4
5
[
  [15,7],
  [9,20],
  [3]
]

这道题实质上就上一道题(102)，只用将list每层从0添加即可，即一个反转过程，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<List<Integer>> levelOrderBottom(TreeNode root) {
    LinkedList<List<Integer>> lists=new LinkedList<>();
    addLevel(lists,0,root);
    return lists;
}
private void addLevel(LinkedList<List<Integer>> lists, int i, TreeNode root) {
    if(root==null)return;
    if(i>=lists.size())lists.addFirst(new LinkedList<Integer>());
    lists.get(lists.size()-i-1).add(root.val);
    addLevel(lists,i+1,root.left);
    addLevel(lists,i+1,root.right);
}

[leetcode 199] Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,

1
2
3
4
5
   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

这道题虽然是medium，但是如果知道如何使用递归的方法实现层次遍历，那么就会发现非常的简单，用一个变量来记录当前的层，每次都从节点的右子树遍历，当该子树不为空得时候就将该节点添加到list中，只有当list的大小小于层数时，才添加，这就保证了每次都是将每层的最右边的节点添加进来。

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<Integer> rightSideView(TreeNode root) {
    List<Integer> list=new ArrayList<>();
    helper(list,root,1);
    return list;
}
private void helper(List<Integer> list, TreeNode root, int i) {
    if(root!=null){
        if(list.size()<i)list.add(root.val);
        helper(list,root.right,i+1);
        helper(list,root.left,i+1);
    }
}

待续…

如果觉得有帮助，给我打赏吧！