Java描述 LeetCode，94，145，144 二叉树的递归和非递归表示

大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞是我的最大动力，如有错误还请不吝赐教，万分感谢。一起支持原创吧！纯手打有笔误还望谅解。

☘️重新回忆下递归需要注意的事情：

• 递归体，就是一次执行的逻辑
• 终止条件
• 函数的返回值和参数，如果有一个参数全局使用，就需要放入到递归函数的参数

// root left right
public static void preOrderTraverse(Node root, List nodes) {
    if (root == null) {
        return;
    }
    nodes.add(root);
    preOrderTraverse(root.left, nodes);
    preOrderTraverse(root.right, nodes);
}

// left root right
public static void inOrderTraverse(Node root, List nodes) {
    if (root == null) {
        return;
    }
    inOrderTraverse(root.left, nodes);
    nodes.add(root);
    inOrderTraverse(root.right, nodes);
}

// left  right root
public static void postOrderTraverse(Node root, List nodes) {
    if (root == null) {
        return;
    }
    postOrderTraverse(root.left, nodes);
    postOrderTraverse(root.right, nodes);
    nodes.add(root);
}

☘️非递归这里就需要注意下了，三种非递归，先序，中序代码几乎差不多，后序需要稍微注意一下

☘️先序：根左右，核心思想是遇见根就可以输出了，我们用一个cur代表遍历指针，根据顺序，我们知道始终先遍历左边的，再遍历右边的。所以当有左子树的时候就可以一直压入栈中。由于是先序，根优先遍。所以遍历左子树的根的时候就可以放入遍历list中。

// root left right 非递归
public static void preOrderTraverse2(Node root, List nodes) {
    Stack stack = new Stack<>();
    Node cur = root;
    while (cur != null || !stack.empty()) {
        if (cur != null) {
            nodes.add(cur);
            stack.push(cur);
            cur = cur.left;
        } else {
            cur = stack.pop();
            cur = cur.right;
        }
    }
}

☘️中序：左根右，和先序的区别就在于，访问节点的时机，中序需要先访问左孩子，左孩子没有的情况下，访问根，所以我们可以继续利用上面的代码，当不存在左孩子的时候，出栈一个节点，这个节点就是根节点，加入到list中，代码如下：

// left root right 非递归
public static void inOrderTraverse2(Node root, List nodes) {
    Stack stack = new Stack<>();
    Node cur = root;
    while (cur != null || !stack.empty()) {
        if (cur != null) {
            stack.push(cur);
            cur = cur.left;
        } else {
            cur = stack.pop();
            nodes.add(cur);
            stack.push(cur.right);
        }
    }
}

☘️后序遍历是值得说一说的地方，后序遍历，左右根，我们继续沿用上面的模版，想清楚一件事情，什么时候一个节点可以输出呢？一个节点作为根节点，左右孩子都必须输出了它才能输出，按照模版，一直向左遍历，遇到了空节点，也就是说没有左孩子了，那么右孩子可能有也可能没有

• 如果没有，就可以直接访问这个根节点
• 如果有，就得在右孩子访问过的情况下我才能输出，也就是说，访问根节点的时候，上一个被访问到的节点刚好是根节点的右孩子就行。

// left right root 非递归，
public static void postOrderTraverse3(Node root, List nodes) {
    Stack stack = new Stack<>();
    Node cur = root;
    Node pre = null; // store previous visited node
    while (cur != null || !stack.empty()) {
        if (cur != null) {
            stack.push(cur);
            cur = cur.left;
        } else {
            cur = stack.pop();
            // two conditions:
            //   - don't have right node
            //   - right node has been visited
            if (cur.right == null || pre == cur.right) {
                // visit node
                nodes.add(cur);
                pre = cur;
                cur = null; // cur has been bushed into the stack in the past, pop the top of stack directly
            } else {
                // push the popped root into stack
                stack.push(cur);
                cur = cur.right;
            }
        }
    }
}

☘️后序，根左右，还记得先序的顺序吗？左右根，先序是一直访问左子树，如果我们一直访问右子树，不就得到右左根的序列了吗？有了右左根，我们逆序以下，不就变成根左右了吗？
代码：

// left right root 非递归，
// first step: root right left
// second step: post order output nodes
public static void postOrderTraverse2(Node root, List nodes) {
   Stack stack = new Stack<>();
   Node cur = root;
   while (cur != null || !stack.empty()) {
       if (cur != null) {
           stack.push(cur);
           nodes.add(cur);
           cur = cur.right;
       } else {
           cur = stack.pop();
           cur = cur.left;
       }
   }
}