二叉树遍历的那些事

定义树的节点如下

public class TreeNode {
    public Integer data;
    public TreeNode leftChild;
    public TreeNode rightChild;
}

非递归前序遍历

方法一

考虑一般情况，对于给定的一个节点，可以按下面三个步骤遍历：

1、持续遍历左子节点，直到左子节点为空。
2、弹出栈顶元素，访问它的右子节点。
3、继续第一步，直到栈空。

public List<TreeNode> preOrder(TreeNode root) {
    List<TreeNode> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    TreeNode cur = root;
    Deque<TreeNode> stack = new LinkedList<>();
    while (cur != null || !stack.isEmpty()) {
        // 持续遍历左子树，直到左子树为空
        while (cur != null) {
            result.add(cur);
            stack.push(cur);
            cur = cur.leftChild;
        }
        if (!stack.isEmpty()) {
            cur = stack.pop();
            cur = cur.rightChild;
        }
    }

    return result;
}

方法二

根据栈的弹出顺序来遍历，考虑下面三个步骤

1、利用给定的节点初始化栈，保证栈不为空。
2、访问栈顶元素，然后将其右子节点、左子节点分别入栈。
3、重复步骤2，直到栈为空。

public List<TreeNode> preOrder(TreeNode root) {
    List<TreeNode> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    TreeNode cur = root;
    Deque<TreeNode> stack = new LinkedList<>();
    // 首先跟节点入栈，保证栈不为空
    stack.push(cur);
    while (!stack.isEmpty()) {
        // 访问栈顶元素
        cur = stack.pop();
        result.add(cur);
        // 右子节点、左子节点分别入栈
        if (cur.rightChild != null) {
            stack.push(cur.rightChild);
        }
        if (cur.leftChild != null) {
            stack.push(cur.leftChild);
        }
    }

    return result;
}

非递归中序遍历

这里采用的方法与前序遍历中介绍的第一种方法类似：

1、持续遍历左子节点，只入栈不访问，直到左子节点为空。
2、弹出栈顶元素，这个时候访问该节点，访问它的右子节点。
3、继续第一步，直到栈空。

public List<TreeNode> inOrder(TreeNode root) {
    List<TreeNode> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    TreeNode cur = root;
    Deque<TreeNode> stack = new ArrayDeque<>();
    while (cur != null || !stack.isEmpty()) {
        // 只入栈，不访问
        while (cur != null) {
            stack.push(cur);
            cur = cur.leftChild;
        }
        // 出栈的时候访问
        if (!stack.isEmpty()) {
            cur = stack.pop();
            result.add(cur);
            cur = cur.rightChild;
        }
    }

    return result;
}

非递归后序遍历

非递归遍历被称为三种遍历中最难的一个，这里，我们分别用三种方法来实现

方法一

后序遍历可以看做是从右到左的先序遍历的逆过程，所以可以利用辅助栈，按照从右至左的先序遍历，遍历的结果存到辅助栈里，然后将辅助栈的元素依次出栈。

public List<TreeNode> postOrder(TreeNode root) {
    List<TreeNode> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    TreeNode cur = root;
    // 辅助栈
    Deque<TreeNode> assistStack = new ArrayDeque<>();
    // 用于保存从右到左先序遍历节点的栈
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(cur);

    while (!stack.isEmpty()) {
        cur = stack.pop();
        assistStack.push(cur);
        if (cur.leftChild != null) {
            stack.push(cur.leftChild);
        }
        if (cur.rightChild != null) {
            stack.push(cur.rightChild);
        }
    }
    // 将辅助栈元素依次出栈
    while (!assistStack.isEmpty()) {
        cur = assistStack.pop();
        result.add(cur);
    }
    return result;
}

方法二

对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点。

此时该结点出现在栈顶，但是此时不能将其出栈并访问，因为其右孩子还未被访问。所以，接下来按照相同的规则对其右子树进行相同的处理。当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。

在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。

public List<TreeNode> postOrder3() {
    List<TreeNode> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    // 用来保存当前节点是第几次访问
    Map<TreeNode, Integer> visitedNodes = new HashMap<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            visitedNodes.put(cur, 1);
            stack.push(cur);
            cur = cur.leftChild;
        }

        if (!stack.isEmpty()) {
            cur = stack.pop();
            int visitCount = visitedNodes.getOrDefault(cur, 0);
            // 第二次出现在栈顶才访问
            if (visitCount < 2) {
                visitedNodes.put(cur, visitCount + 1);
                stack.push(cur);
                cur = cur.rightChild;
            } else {
                result.add(cur);
                cur = null;
            }
        }
    }
    return result;
}

方法三

根据后续遍历的访问情况，我们可以总结出一般规律，对于任一结点P，有且只有两种情况下才可以对其访问：

1、如果P不存在左孩子和右孩子，则可以直接访问它；

2、P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。

若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。

public List<TreeNode> postOrder4() {
    List<TreeNode> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    TreeNode cur = root;
    // 保存上一个访问的节点，
    // 用来判断上一个访问的节点是不是当前节点的左子节点或右子节点
    TreeNode pre = null;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(cur);
    while (!stack.isEmpty()) {
        cur = stack.peek();
        // 1）叶子节点直接访问
        // 2）如果当前节点要被加到result中，则一定满足：
        //     1、左子节点刚刚被添加（没有右子节点的情况）
        //     2、右子节点刚刚被添加（有或没有左子节点）
        if ((cur.leftChild == null && cur.rightChild == null) ||
            (pre != null && (pre == cur.leftChild || pre == cur.rightChild))) {
            result.add(cur);
            stack.pop();
            pre = cur;
        } else {
            if (cur.rightChild != null) {
                stack.push(cur.rightChild);
            }
            if (cur.leftChild != null) {
                stack.push(cur.leftChild);
            }
        }
    }
    return result;
}

按层遍历二叉树

考虑使用一个队列作为辅助容器，然后将根节点首先入队，接下来按下面三个步骤执行：

1、队列不为空，从队列头部取出一个节点，打印该节点。

2、如果该节点有左子节点，则将左子节点放入队尾，如果有右子节点，则将右子节点也放入队列队尾。

3、重复步骤1。

public List<TreeNode> deepOrder(TreeNode root) {
    List<TreeNode> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    TreeNode cur = root;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(cur);

    while (!queue.isEmpty()) {
        cur = queue.poll();
        result.add(cur);
        if (cur.leftChild != null) {
            queue.add(cur.leftChild);
        }
        if (cur.rightChild != null) {
            queue.add(cur.rightChild);
        }
    }
    return result;
}

打印指定层的节点

方法一

我们上面已经实现了二叉树的按层遍历，如果我们在访问节点时能够知道当前节点处于哪一层，那么问题迎刃而解。

为了能够“知道”当前节点处的层次，可以考虑使用一个Map来保存每个节点的层次信息。

public List<TreeNode> visitSpecifiedLevel(int level) {
    if (level <= 0 || root == null) {
        return Collections.emptyList();
    }

    List<TreeNode> result = new ArrayList<>();
    
    TreeNode cur = root;
    // 存储节点层级的map
    Map<TreeNode, Integer> levelMap = new HashMap<>();
    
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(cur);
    // 根节点为第一层
    levelMap.put(cur, 1);

    while (!queue.isEmpty()) {
        cur = queue.poll();
        int curLevel = levelMap.get(cur);
        if (curLevel == level) {
            result.add(cur);
        } else if (curLevel < level) {
            if (cur.leftChild != null) {
                queue.add(cur.leftChild);
                levelMap.put(cur.leftChild, curLevel + 1);
            }
            if (cur.rightChild != null) {
                queue.add(cur.rightChild);
                levelMap.put(cur.rightChild, curLevel + 1);
            }
        } else {
            break;
        }
    }
    return result;
}

方法二

采用递归，不需要任何辅助容器：

public List<TreeNode> visitSpecifiedLevel2(int level) {
    if (level <= 0 || root == null) {
        return Collections.emptyList();
    }
    return subVisit(Collections.singletonList(root), level, 1);
}

public List<TreeNode> subVisit(List<TreeNode> parentNodes, int level, int curLevel) {
    if (level == curLevel) {
        return parentNodes;
    } 
    List<TreeNode> result = new ArrayList<>();
    for (TreeNode node: parentNodes) {
        if (node.leftChild != null) {
            result.add(node.leftChild);
        }
        if (node.rightChild != null) {
            result.add(node.rightChild);
        }
    }
    return subVisit(result, level, curLevel + 1);
}

获取二叉树的深度

所谓树的深度，就是从根节点到叶子节点的所有路径中，最长的那个路径的长度。

考虑一般情况，如果一棵树只有一个根节点，那么他的深度是1，如果根节点有左子树或右子树，那么树的深度应该是左子树或右子树深度较大的那个值再加上1。

利用递归，很容易实现上面的思路：

private int deep(TreeNode parent) {
    int leftDeep = 0;
    int rightDeep = 0;
    if (parent.leftChild != null) {
        leftDeep = deep(parent.leftChild);
    }
    if (parent.rightChild != null) {
        rightDeep = deep(parent.rightChild);
    }
    return leftDeep > rightDeep ? rightDeep + 1 : leftDeep + 1;
}

路径求和

从根节点到某个叶子节点，途中经过的所有节点形成一条路径。如果给定一个值，我们如何找到节点之和等于该值的所有路径呢？

可以考虑先序遍历，具体分为下面几个步骤

1、采用先序遍历，并记录当前栈中元素之和。当到达叶子节点时，判断栈内元素之和是否与给定值相等。

2、如果相等，则打印栈中所有元素，不满足则执行第三步。

3、弹出栈顶元素，然后看其是否有右孩子，如果有，则执行第一步，如果没有则继续弹栈。

public static void print2(TreeNode root, int sum) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    int curSum = 0;
    subPrint2(root, sum, curSum, stack);
}

private static void subPrint2(TreeNode root, int sum, int curSum, Deque<TreeNode> stack) {
    stack.push(root);
    curSum += root.data;

    boolean isLeaf = root.leftChild == null && root.rightChild == null;
    // 叶子节点，并且路径之和与给定值相等
    if (isLeaf && sum == curSum) {
        Iterator<TreeNode> it = stack.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
        System.out.println("--- split line ---");
    }

    if (root.leftChild != null) {
        subPrint2(root.leftChild, sum, curSum, stack);
    }

    if (root.rightChild != null) {
        subPrint2(root.rightChild, sum, curSum, stack);
    }
    // 弹出栈顶元素，并减少curSum值
    TreeNode poped = stack.pop();
    curSum -= poped.data;
}

完！