算法思维训练（七）| 树🎈 - 🥕萝卜兔农场🐇|拾荒基地

一、树基础知识

1. 树概念

树是算法面试经常遇到的数据结构之一，在实际工作中也有可能经常用到。在一棵非空的树中有一个根节点，这个节点下面可能有若干子节点，每个子节点下面还有其他的子节点。如果一个节点没有子节点，那么它就是一个叶节点。
二叉树是经典的树结构之一，在二叉树中每个节点最多只有两个子节点，可以分别把它们称为左子节点和右子节点。二叉树的根节点没有父节点，一棵非空二叉树只有一个父节点，二叉树的叶节点没有子节点。
二叉树是一种典型的具有递归性质的数据结构。二叉树的根节点可能有子节点，子节点又是对应子树的根节点，它可能也有自己的子节点。由于二叉树本身就是递归的数据结构，因此很多与二叉树相关的问题用递归的代码解决会更加的直观。

2. 二叉树类样例

/**
 * 二叉树节点
 * @author nepakina
 */
public class TreeNode {
    public int val = 0;
    public TreeNode left = null;
    public TreeNode right = null;

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

二、知识扩展 & 练习

1. 二叉树的深度优先搜索

知识扩展

二叉树的深度优先搜索又可以细分为中序遍历、前序遍历和后序遍历。
一般的，我们可以通过递归的方式实现不同方式的遍历。但递归无法很好的解决多层数的二叉树导致的调用栈溢出问题。二叉树的遍历往往可以借助栈来实现，通过在不同的时机将元素放入栈或者出栈，可以很好的模拟前、中、后序遍历。

Ⅰ. 中序遍历

根节点在中间的遍历方式：先遍历二叉树的左子树，然后遍历二叉树的根节点，最后遍历二叉树的右子树。
递归的思路这里不做过多解释。此时的栈的解决思路其实非常简单，因为是中序遍历，左节点要优先遍历，所以先依次遍历左节点，并将其翻入栈，直到不再有子节点时，将节点放入序列，再从栈中获取父节点，处理父节点的右节点。右节点依旧是优先处理左节点，并依次入栈。如此循环，直到最后栈中不再有元素。

/**
 * 中序遍历:递归
 * @param root 根节点
 * @return 结果
 */
public List<Integer> inorderTraversalByRecursion(TreeNode root) {
    List<Integer> nodes = new ArrayList<>();
    dfs(root, nodes);
    return nodes;
}

/**
 * 递归中序遍历
 * @param node 根节点
 * @param nodes 结果
 */
public void dfs(TreeNode node, List<Integer> nodes) {
    if (node != null) {
        // 先处递归处理左节点，再处理自身，最后处理右节点
        dfs(node.left, nodes);
        nodes.add(node.val);
        dfs(node.right, nodes);
    }
}

/**
 * 中序遍历：栈
 * @param root 根节点
 * @return 结果
 */
public List<Integer> inorderTraversalByStack(TreeNode root) {
    List<Integer> nodes = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        // 顺着节点的左节点一直遍历
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        // 取出节点，当作根节点，随后遍历右节点
        cur = stack.pop();
        nodes.add(cur.val);
        cur = cur.right;
    }
    return nodes;
}

Ⅱ. 前序遍历

根节点在前面的遍历方式：先遍历二叉树的根节点，再遍历二叉树的左子树，最后遍历二叉树的右子树。
递归的代码中，只需要更改一下代码顺序即可。而栈也只需要将添加元素放入到遍历左节点的代码块内即可。

public List<Integer> preorderTraversalByRecursion(TreeNode root) {
    // ...
}
public void dfs(TreeNode node, List<Integer> nodes) {
    if (node != null) {
        nodes.add(node.val);
        dfs(node.left, nodes);
        dfs(node.right, nodes);
    }
}

public List<Integer> preorderTraversalByStack(TreeNode root) {
    // ...
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            nodes.add(cur.val);
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        cur = cur.right;
    }
    // ...
}

Ⅲ. 后序遍历

根节点在后面的遍历方式：先遍历左子树，再遍历右子树，最后遍历根节点。
同理，递归只需要略微更改一下代码顺序即可。而栈需要对逻辑进行调整，遍历过程中，对元素的左右节点遍历，并记录上一个遍历的节点，如果当前节点的右节点是上一个遍历的节点，说明以当前节点为根节点的字节点已经遍历过了，按照左右中的顺序，下一个遍历的应该是当前节点。否则应该对右节点进行入栈遍历，如此往复，最终即可得到遍历序列。

public List<Integer> postorderTraversalByRecursion(TreeNode root) {
    // ...
}
public void dfs(TreeNode node, List<Integer> nodes) {
    if (node != null) {
        dfs(node.left, nodes);
        dfs(node.right, nodes);
        nodes.add(node.val);
    }
}

/**
 * 后序遍历：栈
 * @param root 根节点
 * @return 结果
 */
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> nodes = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    // 记录上一个加入返回值集合的节点，pre 用于判断是否已经完成右节点的遍历，
    // 如果完成，pre 会等于其右节点，此时下一个遍历的应该是当前节点
    TreeNode pre = null;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.peek();
        // 如果右边节点为空，则左右中变为左中，或者右边节点为上一个节点（左右已经遍历）
        // 此时处理根节点
        if (cur.right == null || cur.right == pre) {
            stack.pop();
            nodes.add(cur.val);
            pre = cur;
            cur = null;
        } else {
            cur = cur.right;
        }
    }
    return nodes;
}

题目练习

Ⅰ：二叉树剪枝

题目描述

一棵二叉树的所有节点的值要么是 0 要么是 1，请剪除该二叉树中所有节点的值全都是 0 的子树。例如，在剪除图 7.1(a) 中二叉树中所有节点值都为 0 的子树之后的结果如图 7.1(b) 所示。
图 7.1