Java如何實現遞歸？
在Java中，二叉樹的后序遍歷可以使用遞歸或迭代的方式進行實現。
遞歸實現
遞歸實現后序遍歷的思路是先遞歸訪問當前節(jié)點的左子樹，再遞歸訪問右子樹，最后訪問當前節(jié)點本身。
下面是一個遞歸實現的示例代碼：
public void postOrderTraversal(TreeNode root) {
? ?if (root != null) {
? ? ? ?postOrderTraversal(root.left);
? ? ? ?postOrderTraversal(root.right);
? ? ? ?System.out.print(root.val + " ");
? ?}}
在上述代碼中，postOrderTraversal()方法是一個遞歸方法，它首先遞歸訪問當前節(jié)點的左子樹，然后遞歸訪問右子樹，最后訪問當前節(jié)點本身。
迭代實現
迭代實現后序遍歷的思路是使用棧來保存待訪問的節(jié)點。首先將根節(jié)點入棧，然后循環(huán)執(zhí)行以下操作：
從棧頂取出一個節(jié)點，如果該節(jié)點沒有子節(jié)點或者其子節(jié)點已經被訪問過，則訪問該節(jié)點并將其從棧中彈出；
如果該節(jié)點有子節(jié)點且子節(jié)點尚未被訪問過，則依次將其右子節(jié)點、左子節(jié)點入棧。
下面是一個迭代實現的示例代碼：
public void postOrderTraversal(TreeNode root) {
? ? Stack<TreeNode> stack = new Stack<>();
? ? TreeNode lastVisited = null; // 記錄上一個訪問的節(jié)點
? ? while (root != null || !stack.isEmpty()) {
? ? ? ? // 將左子節(jié)點入棧
? ? ? ? if (root != null) {
? ? ? ? ? ? stack.push(root);
? ? ? ? ? ? root = root.left;
? ? ? ? }
? ? ? ? else {
? ? ? ? ? ? TreeNode peekNode = stack.peek();
? ? ? ? ? ? // 如果該節(jié)點沒有右子節(jié)點或者右子節(jié)點已經被訪問過，則訪問該節(jié)點并將其從棧中彈出
? ? ? ? ? ? if (peekNode.right == null || peekNode.right == lastVisited) {
? ? ? ? ? ? ? ? System.out.print(peekNode.val + " ");
? ? ? ? ? ? ? ? lastVisited = stack.pop();
? ? ? ? ? ? }
? ? ? ? ? ? // 否則將右子節(jié)點入棧
? ? ? ? ? ? else {
? ? ? ? ? ? ? ? root = peekNode.right;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
在上述代碼中，postOrderTraversal()方法是一個迭代方法，它使用了一個棧來保存待訪問的節(jié)點，并使用lastVisited變量來記錄上一個訪問的節(jié)點。在循環(huán)中，如果當前節(jié)點沒有左子節(jié)點，則從棧頂取出一個節(jié)點并訪問它；否則將左子節(jié)點入棧。如果當前節(jié)點沒有右子節(jié)點或者右子節(jié)點已經被訪問過，則訪問該節(jié)點并將其從棧中彈出；否則將右子節(jié)點入棧。
