算法：二叉树遍历类题目

作者: Tim在路上 | 来源:发表于2022-02-12 18:42 被阅读0次

算法：二叉树遍历类题目

树的遍历顺序是依赖于 根 节点的位置，前序遍历的顺序为 根左右，中序遍历的顺序为 左根右，后序遍历的顺序为 左右根。除此以外还存在层次遍历。

在树类算法中，很多题目是基于树的遍历和树的性质而产生的，熟悉树的遍历和性质是灵活应用树类题目的前提。

那么什么是树和二叉树？

树（tree）是n（n>=0）个结点的有穷集。n=0时称为空树。在任意一个非空树中：（1）每个元素称为结点（node）；（2）仅有一个特定的结点被称为根结点或树根（root）。（3）当n>1时，其余结点可分为m（m≥0）个互不相交的集合T1，T2，……Tm，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作根的子树（subtree）。可见树（tree）的定义本身就是迭代递归的定义。

二叉树是树中节点的度不大于2的有序树，它是一种最简单且最重要的树。

1. 前根遍历

1.1 前根的递归遍历

由树的定义可知，树天生具有可迭代的特性。

   // 由于方法中要方法结果列表，不可直接进行迭代，可以定义全局列表，或定义helper方法。
   List<Integer> res = new ArrayList<>(); 
   public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
          return res;
        }
        // 先打印根节点，然后打印左子树，最后再打印右子树
        res.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return res;
    }

1.2 前根的迭代遍历

递归一般可以通过栈来进行描述，所以可以通过栈实现前根的迭代遍历。

  public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
          return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.empty()) {
            if (cur != null) {
                res.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode node = stack.pop();
                if(node.right != null) {
                    cur = node.right;
                }
            }
        }
        return res;
    }

这种方式是使用先遍历左子树，如果左子树为NULL, 则回退到存在的右节点，再遍历其左子树。

  public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while(!stack.empty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            // 先压入右节点，再压入左节点
            if (node.right != null) {
                stack.add(node.right);
            }
            if (node.left != null) {
                stack.add(node.left);
            }
        }
        return res;
    }

也可以采用在压栈时，先压入右节点，再压入左节点。这样在弹出时可以按照先序遍历的顺序从左到右进行弹出。

2. 中根遍历

2.1 中根的递归遍历

   // 由于方法中要方法结果列表，不可直接进行迭代，可以定义全局列表，或定义helper方法。
   List<Integer> res = new ArrayList<>(); 
   public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
          return res;
        }
        inorderTraversal(root.left);
        // 先打印根节点，然后打印左子树，最后再打印右子树
        res.add(root.val);
        inorderTraversal(root.right);
        return res;
    }

2.2 中根的迭代遍历

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
          return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.empty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode node = stack.pop();
                res.add(node.val);
                if(node.right != null) {
                    cur = node.right;
                }
            }
        }
        return res;
    }

中根遍历可以先压左节点，再压右节点。再回退弹出时将其放入列表。

3. 后根遍历

3.1 后根的递归遍历

   // 由于方法中要方法结果列表，不可直接进行迭代，可以定义全局列表，或定义helper方法。
   List<Integer> res = new ArrayList<>(); 
   public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) {
          return res;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        // 先打印根节点，然后打印左子树，最后再打印右子树
        res.add(root.val);
        return res;
    }

3.2 后根的迭代遍历

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null) return res;
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            res.add(cur.val);
            if(cur.left!=null) stack.push(cur.left);
            if(cur.right!=null) stack.push(cur.right);
        }
        Collections.reverse(res);
        return res;
    }

可以采用先压左节点，再压右节点，最后再进行反转列表。另外如果使用的是LinkedList<>，则可以使用addFirst的方法。

public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null) return res;

        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            res.addFirst(cur.val);
            if(cur.left != null) stack.push(cur.left);
            if(cur.right != null) stack.push(cur.right);
        }
        return res;
    }

另外可以将每一个父节点后加一个NULL节点作为标识，在弹出时将其添加到结果List中。

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.add(root);
    while(!stack.empty()) {
        TreeNode node = stack.pop();
        if (node != null) {
            // 将每一个父节点重新压入， 这里相当于进行了两遍的压栈
            stack.push(node);
            stack.push(null);
            if (node.right != null) {
                stack.add(node.right);
            }
            if (node.left != null) {
                stack.add(node.left);
            }
        } else {
            // 将父节点进行添加
            TreeNode r = stack.pop();
            res.add(r.val);
        }
    }
    return res;
}

4. 层次遍历

4.1 基于递归的层次遍历

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    levelHelper(res, root, 0);
    return res;
}

private void levelHelper(List<List<Integer>> res, TreeNode root, int level) {
    if (root == null)
        return;
    // level表示的是层数，如果level >= list.size()，说明到下一层了，所以
    // 要先把下一层的list初始化，防止下面add的时候出现空指针异常
    if (level >= res.size()) {
        res.add(new ArrayList<>());
    }
    // level表示的是第几层，这里访问到第几层，我们就把数据加入到第几层
    res.get(level).add(root.val);
    // 当前节点访问完之后，再使用递归的方式分别访问当前节点的左右子节点
    levelHelper(res, root.left, level + 1);
    levelHelper(res, root.right, level + 1);
}

传入参数为结果list, 遍历节点root, 和遍历的层数level。如果level大于等于res列表中的。

4.2 基于迭代的层次遍历

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> list = new ArrayList<>();
        for (int i=0;i < size; i++) {
            TreeNode node = queue.poll();
            list.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        result.add(list);
    }
    return result;
}

使用queue的先进先出的性质，进行层次遍历。

基于树的递归应用问题

由树的定义可知，树的定义是递归的，所以可以通过递归去解决一些类树的问题。使用递归解决问题一般有两种思路：1. 自顶向下。2. 自底向上。

自顶向下意味着在每一个递归层级，先方法当前节点应用计算一些值。
自底向上意味着先进行递归遍历，利用递归的回溯的原理，在递归的回溯过程中应用计算。

二叉树的最大深度

自顶向下：

int maxDepth = 0;
public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    callDepth(root, 1);
    return maxDepth;
}

private void callDepth(TreeNode root, int level) {
    // 处理特殊null节点，返回特定值。
    if (root == null) {
        return;
    }
    // 如果当前节点满足条件，更新结果值
    if (root.left == null && root.right == null) {
        maxDepth = Math.max(maxDepth, level);
    }
    // 左右子树进行递归
    callDepth(root.left, level + 1);
    callDepth(root.right, level + 1);
}

自底向上：

public int maxDepth(TreeNode root) {
  // 处理特殊的null节点，返回特定值
  if (root == null) {
      return 0;
  }
  // 处理特定值作为递归出口值
  if (root.left == null && root.right == null) {
      return 1;
  }
  // 左右子树进行递归
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

对称的二叉树

自顶向下：

public boolean isSymmetric(TreeNode root) {
   if (root == null) {
       return false;
   }
   return isSymmetricCore(root.left, root.right);
}

private boolean isSymmetricCore(TreeNode left, TreeNode right) {
    if (left == null && right == null) {
        return true;
    }
    if (left == null || right == null || left.val != right.val) {
        return false;
    }
    return isSymmetricCore(left.left, right.right) && isSymmetricCore(left.right, right.left);
}

路径总和

自低向上

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) {
        return false;
    }
    if (root.left == null && root.right == null) {
        return targetSum == root.val;
    }
    return hasPathSum(root.left, targetSum - root.val) ||
    hasPathSum(root.right, targetSum - root.val);
}

由中序和后序遍历构造二叉树

自顶向下：

public TreeNode buildTree(int[] inorder, int[] postorder) {
    if (postorder.length == 0) {
        return null;
    }
    int len = postorder.length;
    return buildTreeCore(inorder, 0, len - 1, postorder, 0, len - 1);
}

private TreeNode buildTreeCore(int[] inorder, int s1, int e1, int[] postorder, int s2, int e2) {
    if (s2 > e2) {
        return null;
    }
    int rootVal = postorder[e2];
    TreeNode root = new TreeNode(rootVal);
    // 算出当前根节点到s1的距离
    int mid = 0;
    while (inorder[s1 + mid] != rootVal) mid++;
    root.left = buildTreeCore(inorder, s1, s1 + mid - 1, postorder, s2, s2 + mid - 1);
    root.right = buildTreeCore(inorder, s1 + mid + 1, e1, postorder, s2 + mid, e2 - 1);
    return root;
}

由前序和中序遍历生成二叉树

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0) {
        return null;
    }
    int len = preorder.length;
    return buildTreeCore(preorder, 0, len - 1, inorder, 0, len - 1);
}

private TreeNode buildTreeCore(int[] preorder, int s1, int e1, int[] inorder, int s2, int e2) {
    if (s1 > e1) {
        return null;
    }
    int rootVal = preorder[s1];
    TreeNode root = new TreeNode(rootVal);
    if (s1 == e1) {
        return root;
    }
    // 算出当前根节点到s1的距离
    int mid = 0;
    while (inorder[s2 + mid] != rootVal) mid++;
    root.left = buildTreeCore(preorder, s1 + 1, s1 + mid, inorder, s2 , s2 + mid -1);
    root.right = buildTreeCore(preorder, s1 + mid + 1, e1, inorder, s2 + mid + 1, e2);
    return root;
}

由上面的题目可以看出，大部分的算法题目都可以通过这两种方法实现。但是两种方式并不能适应于所有的题目。如果题目可以在当前的任意节点就可以判断出返回的结果，则适合使用自顶向下（增加剪枝效果）。如果题目必须遍历到叶子节点后才能计算出中间值，则需要使用自底向上。当然如果是根据叶子节点的值的状态，或者在遍历过程中并不需要更新结果值，那么这两种方式其实是很混淆的。

基于树的迭代应用问题

基于迭代进行处理，一般围绕层次遍历，先序，后序遍历或中序的迭代遍历进行展开的。

二叉树的最大深度

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int count = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        while (size -- > 0) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        count ++;
    }
    return maxDepth;
}

使用层次遍历的方式实现获取二叉树的深度的算法。

镜像二叉树

public boolean isSymmetric2(TreeNode root) {
    if (root == null) {
        return false;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root.left);
    queue.add(root.right);
    while (!queue.isEmpty()) {
        TreeNode left = queue.poll();
        TreeNode right = queue.poll();

        if (left == null && right == null) {
            continue;
        }
        if (left == null || right == null || left.val != right.val) {
            return false;
        }

        queue.add(left.left);
        queue.add(right.right);
        queue.add(left.right);
        queue.add(right.left);
    }
    return false;
}

只判断为false的情况，为true的情况下进行跳过。

路径总和

public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()) {
            TreeNode node = stack.pop();
            if (node.left == null && node.right == null) {
                if (targetSum == node.val) return true;
            }
            if (node.left != null) {
                node.left.val = node.left.val + node.val;
                stack.push(node.left);
            }
            if (node.right != null) {
                node.right.val = node.right.val + node.val;
                stack.push(node.right);
            }
        }
        return false;
    }

由于只使用一次，所以可以使用TreeNode 的val作为临时存储值的地方。

算法：二叉树遍历类题目

算法：二叉树遍历类题目

1. 前根遍历

2. 中根遍历

3. 后根遍历

4. 层次遍历

基于树的递归应用问题

基于树的迭代应用问题

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

算法与实战