每日一算法:树遍历相关算法

2023-12-16 09:31:53

标题:深入探究树遍历算法:从前序、中序到后序遍历

引言:
树是计算机科学中一种常见的数据结构,广泛应用于各种算法和应用中。树的遍历是其中最基础也是最重要的操作之一。本篇博客将深入探究树的遍历算法,包括前序遍历、中序遍历和后序遍历,并通过举例说明,帮助读者更好地理解和应用这些算法。

一、前序遍历(Preorder Traversal):
前序遍历是一种深度优先遍历算法,其遍历顺序为“根节点-左子树-右子树”。具体步骤如下:

  1. 访问当前节点。
  2. 递归地前序遍历左子树。
  3. 递归地前序遍历右子树。

举例说明:
假设有如下二叉树:

      A
     / \
    B   C
   / \   \
  D   E   F

按照前序遍历的顺序,遍历结果为:A - B - D - E - C - F。

二、中序遍历(Inorder Traversal):
中序遍历是一种深度优先遍历算法,其遍历顺序为“左子树-根节点-右子树”。具体步骤如下:

  1. 递归地中序遍历左子树。
  2. 访问当前节点。
  3. 递归地中序遍历右子树。

举例说明:
以同样的二叉树为例,按照中序遍历的顺序,遍历结果为:D - B - E - A - C - F。

三、后序遍历(Postorder Traversal):
后序遍历是一种深度优先遍历算法,其遍历顺序为“左子树-右子树-根节点”。具体步骤如下:

  1. 递归地后序遍历左子树。
  2. 递归地后序遍历右子树。
  3. 访问当前节点。

举例说明:
继续以相同的二叉树为例,按照后序遍历的顺序,遍历结果为:D - E - B - F - C - A。

四、应用场景:
树的遍历算法在实际应用中有广泛的应用。例如,在二叉搜索树中,中序遍历可以按照升序输出节点值,用于实现有序集合的遍历。前序遍历可以用于构建二叉树的镜像,后序遍历可以用于计算二叉树的深度。

结论:
树的遍历算法是计算机科学中的基础算法之一,掌握了树的遍历算法,能够更好地理解和应用树结构。本篇博客详细介绍了前序遍历、中序遍历和后序遍历算法,并通过举例说明,帮助读者更好地理解和应用这些算法。希望读者能够通过学习本篇博客,对树的遍历算法有更深入的了解。

算法应用举例:
1.恢复二叉搜索树(中序遍历)

问题描述:给你二叉搜索树的根节点 root ,该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下,恢复这棵树 。

实现代码:

TreeNode x = null;

    TreeNode y = null;

    TreeNode pre = null;

    public void recoverTree(TreeNode root) {
        recover(root);
        if(x!=null&&y!=null){
            int temp = x.val;
            x.val = y.val;
            y.val = temp;
        }
    }

    public void recover(TreeNode root) {
        if(root==null){
            return;
        }
        recover(root.left);
        if (pre != null && root.val < pre.val) {
            if (x == null) {
                x = root;
                y = pre;
            } else {
                x = root;
            }
        }
        pre = root;
        recover(root.right);
    }

2.二叉树展开为链表(前序遍历)

问题描述:给你二叉树的根结点 root ,请你将它展开为一个单链表:

展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

实现代码:

/**
     * 二叉树展开为链表
     *
     * @param root
     */
    public static void flatten(TreeNode root) {
        List<TreeNode> result = new ArrayList<>();
        before(root, result);
        for (int i = 0; i < result.size() - 1; i++) {
            TreeNode curr = result.get(i);
            curr.left = null;
            curr.right = result.get(i + 1);
        }
    }

    /**
     * 前序遍历
     *
     * @param node
     * @param result
     */
    public static void before(TreeNode node, List<TreeNode> result) {
        if (node != null) {
            result.add(node);
            before(node.left, result);
            before(node.right, result);
        }
    }

3.翻转二叉树(前序遍历)

问题描述:
给定一棵二叉树的根节点 root,请左右翻转这棵二叉树,并返回其根节点。

实现代码:

/**
     * 翻转二叉树
     *
     * @param root
     * @return
     */
    public static TreeNode invertTree(TreeNode root) {
        reverse(root);
        return root;
    }

    public static void reverse(TreeNode node) {
        if (node == null) {
            return;
        }
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        reverse(node.left);
        reverse(node.right);
    }

4.求二叉树中最大路径和 (后序遍历)

问题描述:
二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ,返回其 最大路径和 。

实现代码:

public static int max = Integer.MIN_VALUE;

    /**
     * 求二叉树中最大路径和
     * @param treeNode
     * @return
     */
    public int maxPathSum(TreeNode treeNode) {
        oneSideMax(treeNode);
        return max;
    }

    /**
     * 以treeNode节点为根节点的子树中寻找以该节点为起点的一条路径,使得该路径上的节点值之和最大。
     * @param treeNode
     * @return
     */
    public static int oneSideMax(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        int leftMax = Math.max(oneSideMax(treeNode.left), 0);
        int rightMax = Math.max(oneSideMax(treeNode.right), 0);
        max = Math.max(max, leftMax + rightMax + treeNode.val);
        return Math.max(leftMax, rightMax) + treeNode.val;
    }

文章来源:https://blog.csdn.net/fudaihb/article/details/134988502
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。