二叉树的遍历

Wu Jun 2019-12-25 15:59:03

Categories： > > Tags：

有两种通用的遍历树的策略：

深度优先搜索（DFS）（栈）
- 在这个策略中，我们采用深度作为优先级，以便从跟开始一直到达某个确定的叶子，然后再返回根到达另一个分支。
- 深度优先搜索策略又可以根据根节点、左孩子和右孩子的相对顺序被细分为先序遍历，中序遍历和后序遍历。
广度优先搜索（BFS）（队列）
- 我们按照高度顺序一层一层的访问整棵树，高层次的节点将会比低层次的节点先被访问到。

前序遍历：根节点->左子树->右子树 [1 2 4 5 3 6]
中序遍历：左子树->根节点->右子树 [4 2 5 1 3 6]
后序遍历：左子树->右子树->根节点 [4 5 2 6 3 1]
层序遍历：[1 2 3 4 5 6]

题目出处

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

1 前序遍历

1.1 递归解法

前序遍历递归解法：

如果二叉树为空，空操作
如果二叉树不为空，访问根节点，前序遍历左子树，前序遍历右子树

public static void preorderTraversalRec(TreeNode root) {
    if (root == null) {
        return;
    }
    System.out.print(root.val + " ");
    preorderTraversalRec(root.left);
    preorderTraversalRec(root.right);
}

1.2 迭代解法

用一个辅助栈，从根节点开始，每次迭代弹出当前栈顶元素，并将其孩子节点压入栈中，先压右孩子再压左孩子。

时间复杂度：访问每个节点恰好一次，时间复杂度为 O(N)。
空间复杂度：取决于树的结构，最坏情况存储整棵树，因此空间复杂度是 O(N)。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        if(null == root){
            return result;
        }

        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);

        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);

            if(null != node.right){
                stack.push(node.right);
            }
            if(null != node.left){
                stack.push(node.left);
            }
        }
        
        return result;
    }
}

1.3 相关试题

1）判断两棵二叉树是否相同

递归解法

如果两棵二叉树都为空，返回真
如果两棵二叉树一棵为空，另一棵不为空，返回假
如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假

迭代解法

前序遍历，对每个节点进行比较

2 中序遍历

2.1 递归解法

中序遍历递归解法

如果二叉树为空，空操作。
如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树

public static void inorderTraversalRec(TreeNode root) {
    if (root == null) {
        return;
    }
    inorderTraversalRec(root.left);
    System.out.print(root.val + " ");
    inorderTraversalRec(root.right);
}

2.2 迭代解法

用栈先把根节点的所有左孩子都添加到栈内，然后输出栈顶元素，再处理栈顶元素的右子树

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        if(null == root){
            return result;
        }

        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode current = root;

        while(true){
            // 先添加一个非空节点所有的左孩子到栈
            while(null != current){
                stack.push(current);
                current = current.left;
            }

            if(stack.isEmpty()){
                break;
            }
            
            // 因为此时已经没有左孩子了，所以输出栈顶元素
            TreeNode node = stack.pop();
            result.add(node.val);
            // 准备处理右子树
            current = node.right;
        }

        return result;
    }
}

3 后序遍历

3.1 递归解法

后序遍历递归解法

如果二叉树为空，空操作
如果二叉树不为空，后序遍历左子树，后序遍历右子树，访问根节点

public static void postorderTraversalRec(TreeNode root) {
    if (root == null) {
        return;
    }
    postorderTraversalRec(root.left);
    postorderTraversalRec(root.right);
    System.out.print(root.val + " ");
}

3.2 迭代解法

后序遍历就是逆前序遍历，前序遍历为 root -> left -> right，后序遍历为 left -> right -> root。可以修改前序遍历成为 root -> right -> left，那么这个顺序就和后序遍历正好相反。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();

        if(null == root){
            return result;
        }

        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        stack.add(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.addFirst(node.val);
            
            if(null != node.left){
                stack.push(node.left);
            }
            if(null != node.right){
                stack.push(node.right);
            }
        }

        return result;
    }
}

4 层序遍历

4.1 递归解法

很少有人会用递归去做 level traversal，基本思想是用一个大的 ArrayList，里面包含了每一层的 ArrayList。大的 ArrayList 的 size 和 level 有关系

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (null == root){
            return levels;
        }
        dfs(root, 0, levels);
        return levels;
    }    
    
    private static void dfs(TreeNode node, int level, List<List<Integer>> levels){
        // 添加一个新的 ArrayList 表示新的一层
        if(level >= levels.size()){
            levels.add(new ArrayList<Integer>());
        }
        // 把节点添加到当前这层的 ArrayList 里
        levels.get(level).add(node.val);
        // 递归处理下一层的左子树和右子树
        if (null != node.left){
            dfs(node.left, level + 1, levels);
        }   
        if (null != node.right){
            dfs(node.right, level + 1, levels);
        }   
    }
}

4.2 迭代解法

相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点，访问，若左子节点或右子节点不为空，将其压入队列

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (null == root) {
            return levels;
        }

        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.addLast(root);
        int level = 0;

        while (!queue.isEmpty()) {
            // 新建本层 List
            levels.add(new ArrayList<Integer>());
            // 当前队列大小就是本层节点的数量
            int level_length = queue.size();
            // 填充本层 List
            for(int i = 0; i < level_length; ++i) {
                TreeNode node = queue.removeFirst();

                levels.get(level).add(node.val);

                if (null != node.left) {
                    queue.addLast(node.left);
                }
                if (null != node.right) {
                    queue.addLast(node.right);
                }
            }
            level++;
        }

        return levels;
    }    
}

4.3 相关试题

1）自底向上的层次遍历

Leetcode 107. 二叉树的层次遍历 II

在层次遍历的基础上，使返回的列表是倒序就行

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> result = new LinkedList<>();
        if(null == root){
            return result;
        }

        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        int level = 0;
        queue.addLast(root);

        while(!queue.isEmpty()){
            result.addFirst(new ArrayList<>());

            int levelSize  = queue.size();
            for(int i = 0; i < levelSize; i++){
                TreeNode node = queue.removeFirst();
                result.get(0).add(node.val);
                if(null != node.left){
                    queue.addLast(node.left);
                }
                if(null != node.right){
                    queue.addLast(node.right);
                }
            }
            levelSize++;
        }

        return result;
    }
}

2）一棵树每层节点的平均数

Leetcode 637. 二叉树的层平均值

问题：给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.

思路：层序遍历，计算每层的平均值

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        if (null == root) {
            return result;
        }

        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.addLast(root);

        while (!queue.isEmpty()) {
            int count = queue.size();
            double sum = 0;
            for(int i = 0; i < count; ++i) {
                TreeNode node = queue.removeFirst();

                sum += node.val;

                if (null != node.left) {
                    queue.addLast(node.left);
                }
                if (null != node.right) {
                    queue.addLast(node.right);
                }
            }
            result.add(sum / count);
        }

        return result;
    }
}

3）得到左下角的节点

Leetcode 513. 找树左下角的值

问题：给定一个二叉树，在树的最后一行找到最左边的值。

思路：层序遍历，从右到左，遍历的最后一个节点就是左下角的节点

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            root = queue.poll();
            if (null != root.right) {
                queue.add(root.right);
            }
            if (null != root.left) {
                queue.add(root.left);
            }
        }
        return root.val;
    }
}

4）求二叉树中的节点个数

递归：
- 如果二叉树为空，节点个数为 0；
- 如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1
迭代：同层序遍历，每次往队列里加节点的时候计数加一

5）二叉树的最大深度

Leetcode 104. 二叉树的最大深度

递归解法

如果二叉树为空，二叉树的深度为 0
如果二叉树不为空，二叉树的深度 = max(左子树深度，右子树深度) + 1

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

迭代解法

层序遍历，每层加一

6）求二叉树第 K 层的节点个数

递归解法

如果二叉树为空或者 k < 1 返回 0
如果二叉树不为空并且 k== 1，返回 1
如果二叉树不为空且 k > 1，返回 root 左子树中 k-1 层的节点个数与 root 右子树 k-1 层节点个数之和

class Solution {
    public static int getNodeNumKthLevelRec(TreeNode root, int k) {
        if (root == null || k < 1) {
            return 0;
        }

        if (k == 1) {
            return 1;
        }

        int numLeft = getNodeNumKthLevelRec(root.left, k - 1);
        int numRight = getNodeNumKthLevelRec(root.right, k - 1);
        return numLeft + numRight;
    }
}

迭代解法

层序遍历，到第 k 层时计数

7）求二叉树中叶子节点的个数

递归解法

若当前节点为空，返回 0
当前节点为叶子节点，返回 1
否则返回左右子树的叶子节点之和

class Solution {
    public int getNodeNumLeafRec(TreeNode root) {
        if (root == null) {
            return 0;
        }
    
        if (root.left == null && root.right == null) {
            return 1;
        }
    
        return getNodeNumLeafRec(root.left) + getNodeNumLeafRec(root.right);
    }
}

迭代解法

层序遍历，如果当前节点没有左右子树，则是叶子节点，计数加一

单链表加法

归并链表