算法-树的遍历和树形动态规划

树的遍历

树节点类

public class TreeNode {

    public int val;

    public TreeNode left;

    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

基于递归的遍历

递归的访问节点的左右孩子，通过调整父节点处理的时机，达到前序、中序、后序遍历的目的

// 前序
public static void firstOrderPrint(TreeNode root) {
    if (root == null) {
        return;
    }
    // 模拟处理
    System.out.print(root.val + " ");
    // ...
    firstOrderPrint(root.left);
    firstOrderPrint(root.right);
}
// 中序
public static void middleOrderPrint(TreeNode root) {
    if (root == null) {
        return;
    }
    middleOrderPrint(root.left);
    // 模拟处理
    System.out.print(root.val + " ");
    // ...
    middleOrderPrint(root.right);
}
// 后序
public static void lastOrderPrint(TreeNode root) {
    if (root == null) {
        return;
    }
    lastOrderPrint(root.left);
    lastOrderPrint(root.right);
    // 模拟处理
    System.out.print(root.val + " ");
    // ...
}

非递归前序遍历

非递归：通过手动压栈，实现递归

使用一个栈，先压入根节点，依次弹出栈顶，每次弹出时先处理当前节点，再按顺序压入其右孩子、左孩子

public static void firstOrderPrintNoRecur(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.add(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        // 先处理父节点
        // 模拟处理
        System.out.print(root.val + " ");
        // ...
        // 先压入右孩子，再压左孩子
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
}

非递归中序遍历

使用一个栈，先压入根节点，从根节点沿着 left 指针持续压入左孩子节点

依次弹出栈顶，每次弹出时先处理当前节点，压入其右孩子，再从右孩子沿着 left 指针持续压入左孩子节点

public static void middleOrderPrintNoRecur(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.add(root);
    while (root.left != null) {
        stack.add(root.left);
        root = root.left;
    }
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        // 先处理父节点
        // 模拟处理
        System.out.print(root.val + " ");
        // ...
        if (node.right != null) {
            node = node.right;
            stack.add(node);
            while (node.left != null) {
                stack.add(node.left);
                node = node.left;
            }
        }
    }
}

非递归后续遍历

使用两个栈，栈 A 压入根节点，依次弹出栈顶，每次先压入栈 B，再按顺序将左孩子、右孩子压入栈 A

相当于栈 B 的入栈顺序是 中-右-左，最后依次弹出栈 B，得到的顺序是 左 - 右 - 中

public static void lastOrderPrintNoRecur(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.add(root);
    while (!stack1.isEmpty()) {
        TreeNode node = stack1.pop();
        stack2.add(node);
        // 先压入左孩子，再压右孩子
        if (node.left != null) {
            stack1.push(node.left);
        }
        if (node.right != null) {
            stack1.push(node.right);
        }
    }
    while (!stack2.isEmpty()) {
        TreeNode node = stack2.pop();
        // 先处理父节点
        // 模拟处理
        System.out.print(root.val + " ");
        // ...
    }
}

宽度优先遍历

宽度优先靠队列

宽度优先遍历，也叫层序遍历、按层遍历

// 返回 Map，key: node，val: 所在层的序号
public static HashMap<TreeNode, Integer> layerPrint(TreeNode root) {
    if (root == null) {
        return null;
    }
    HashMap<TreeNode, Integer> layerMap = new HashMap<>();
    layerMap.put(root, 1);
    int currLayer = 1;
    // 统计每层节点数
    int currLayerNodeNum = 0;
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode curr = queue.poll();
        Integer layer = layerMap.get(curr);
        if (layer == currLayer) {
            currLayerNodeNum++;
        } else {
            currLayer++;
            currLayerNodeNum = 1;
        }
        if (curr.left != null) {
            layerMap.put(curr.left, currLayer + 1);
            queue.add(curr.left);
        }
        if (curr.right != null) {
            layerMap.put(curr.right, currLayer + 1);
            queue.add(curr.right);
        }
        // 模拟处理
        System.out.print(root.val + " ");
        // ...
    }
    return layerMap;
}

判断完全二叉树

完全二叉树，只有最后一层可能不满，但也是从左到右变满，适合用宽度优先遍历

当遇到节点有右无左，则不是完全二叉树

当遇到节点没有左右孩子或者只有左孩子，再之后又遇到孩子不双全的节点，则不是完全二叉树

public static boolean isCBT(TreeNode root) {
    // 是否遇到只有一个左孩子的节点 或 两个孩子都没有的节点
    boolean onlyLeft = false;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode currNode = queue.poll();
        // 有右无左，直接 false
        if (currNode.left == null && currNode.right != null) {
            return false;
        }
        // 已经出现孩子不双全，但又找到有孩子的节点
        if (onlyLeft && currNode.left != null) {
            return false;
        }
        // 出现孩子不双全，标记 onlyLeft
        if (currNode.left == null || currNode.right == null) {
            onlyLeft = true;
        }
        if (currNode.left != null) {
            queue.offer(currNode.left);
        }
        if (currNode.right != null) {
            queue.offer(currNode.right);
        }
    }
    return true;
}

树形动态规划

树形 DP 的含义

DP，动态规划，是一种通过将问题分解成更小的子问题来解决复杂问题的方法。通常用于解决具有重叠子问题和最优子结构性质的问题

树形动态规划是一种特殊的动态规划方法，通常用于解决树形结构的问题

在树形动态规划中，通常会定义一个以树的节点为状态的数组或者其他数据结构，然后通过适当的遍历方式，递归地计算出每个节点的状态，并将状态保存起来供后续使用

判断二叉搜索树

状态数组：isBSTProcess 返回数组 [子树是否是二叉搜索树 0/1, 子树最小值，子树最大值]

最小/最大值：MAX(父节点的值、左子树最小/最大值、右子树最小/最大值)

是否二叉搜索树：

• 左子树不是二叉搜索树或左子树最大值大于等于父节点的值
• 右子树不是二叉搜索树或右子树最小值小于等于父节点的值

public static boolean isBST(TreeNode root) {
    int[] arr = isBSTProcess(root);
    if (arr == null) {
        return false;
    }
    return arr[0] == 1;
}

public static int[] isBSTProcess(TreeNode root) {
    if (root == null) {
        return null;
    }
    int[] lArr = isBSTProcess(root.left);
    int[] rArr = isBSTProcess(root.right);

    int min = root.val;
    int max = root.val;
    if (lArr != null) {
        min = Math.min(min, lArr[1]);
        max = Math.max(max, lArr[2]);
    }
    if (rArr != null) {
        min = Math.min(min, rArr[1]);
        max = Math.max(max, rArr[2]);
    }
    int flag = 1;
    if (lArr != null && (lArr[0] == 0 || lArr[2] >= root.val)) {
        flag = 0;
    }

    if (rArr != null && (rArr[0] == 0 || rArr[1] <= root.val)) {
        flag = 0;
    }
    return new int[]{flag, min, max};
}

判断平衡二叉树

状态数组：isBBTProcess 返回数组 [子树是否是平衡二叉树, 子树的高度]

子树的高度：MAX(左子树高度，右子树高度) + 1

是否是平衡二叉树：左右子树是都平衡二叉树且左右子树高度查小于 2

public static boolean isBBT(TreeNode root) {
    return isBBTProcess(root)[0] == 1;
}

public static int[] isBBTProcess(TreeNode root) {
    if (root == null) {
        // 没有节点时，认为是平衡的
        return new int[]{1, 0};
    }
    int[] lArr = isBBTProcess(root.left);
    int[] rArr = isBBTProcess(root.right);
    int isBalanced = (lArr[0] == 1 && rArr[0] == 1 && Math.abs(lArr[1] - rArr[1]) < 2) ? 1 : 0;
    int height = Math.max(lArr[1], rArr[1]) + 1;
    return new int[]{isBalanced, height};
}

判断满二叉树

状态数组：isFBTProcess返回数组 [子树是否是满二叉树, 子树的高度，子树的节点数]

子树的高度：左右子树高度最大值 + 1

子树的节点树：左右子树节点数之和 + 1

是否满二叉树：左右子树都是满二叉树且当前总节点 n 和高度 h 满足 $n=2^h-1$

public static boolean isFBT(TreeNode root) {
    int[] arr = isFBTProcess(root);
    return arr[0] == 1;
}

public static int[] isFBTProcess(TreeNode root) {
    if (root == null) {
        return new int[]{1, 0, 0};
    }
    int[] lArr = isFBTProcess(root.left);
    int[] rArr = isFBTProcess(root.right);
    int height = Math.max(lArr[1], rArr[1]) + 1;
    int nodes = lArr[2] + rArr[2] + 1;
    int isFull = (lArr[0] == 1 && rArr[0] == 1 && nodes == Math.pow(2, height) - 1)) ? 1 : 0;
    return new int[]{isFull, height, nodes};
}

判断两节点最近公共祖先

后续遍历，只有当节点为 p 或 q 才会返回非 null 值。在递归过程中，如果节点命中 p 或 q 后，会将该节点持续向上抛，最终得到公共祖先节点

当左右子树都返回非 null 值，则当前节点为最近公共祖先

若只有一个子树返回非 null 值，则该子树节点为最近公共祖先

当左右子树都返回 null 值，则在当前节点下未找到合适的

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) {
        return root;
    }

    // 在左子树中寻找 p 或 q
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    // 在右子树中寻找 p 或 q
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    // 如果 p 和 q 分别在左右子树中，则当前节点即为最近公共祖先
    if (left != null && right != null) {
        return root;
    }

    // 如果 p 和 q 都在左子树中，则该子树节点为最近公共祖先
    if (left != null) {
        return left;
    }

    // 如果 p 和 q 都在右子树中，则该子树节点为最近公共祖先
    if (right != null) {
        return right;
    }

    // 如果 p 和 q 都不在左右子树中，则返回 null
    return null;
}