二叉树的遍历

Wu Jun 2020-02-26 11:00:22
01 数据结构与算法 > 算法题 >

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

    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 迭代解法

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

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)自底向上的层次遍历

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

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)一棵树每层节点的平均数

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

思路:层序遍历,计算每层的平均值

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)得到左下角的节点

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

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

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)求二叉树中的节点个数

5)二叉树的最大深度

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

层序遍历,每层加一

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

递归解法
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)求二叉树中叶子节点的个数

递归解法
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);
    }
}
迭代解法

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