首页 > 代码库 > LeetCode解题报告:Binary Tree Postorder Traversal

LeetCode解题报告:Binary Tree Postorder Traversal

2024-07-08 10:57:01   216人阅读

Given a binary tree, return the postorder traversal of its nodes‘ values.

For example:
Given binary tree {1,#,2,3},

   1         2    /   3

 

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

注意：下面是迭代的解法。理解有点困难，和大家讨论一下。

 1 import java.util.ArrayList; 2 import java.util.List; 3 import java.util.Stack; 4  5 /** 6  * Definition for binary tree public class TreeNode { int val; TreeNode left; 7  * TreeNode right; TreeNode(int x) { val = x; } } 8  */ 9 public class TreeNodeNoneReverse {10     List<Integer> postOrder = new ArrayList<Integer>();11 12     public List<Integer> postorderTraversal(TreeNode root) {13         // 非递归实现后序遍历14         TreeNode tempTree = root;15         Stack<TreeNode> stack = new Stack<TreeNode>();16         while (root != null) {17             // 左子树入栈18             for (; root.left != null; root = root.left) {19                 System.out.println("左子树入栈：" + root.val);20                 stack.push(root);21             }22             // 当前节点无右子或右子已经输出23             while (root != null24                     && (root.right == null || root.right == tempTree)) {25                 System.out.println("add list：" + root.val);26                 postOrder.add(root.val);27                 tempTree = root;// 记录上一个已输出节点28                 System.out.println("上一个已输出的节点："+tempTree.val);29                 if (stack.empty()) {30                     System.out.println("stack is empty.");31                     return postOrder;32                 }33                 root = stack.pop();34                 System.out.println("右子树出栈：" + root.val);35             }36             // 处理右子37             System.out.println("处理右子入栈：" + root.val);38             stack.push(root);39             root = root.right;40         }41         System.out.println("可能运行到这儿么？");42         return postOrder;43     }44 45     public static void main(String[] args) {46         TreeNode t1 = new TreeNode(1);47         TreeNode t2 = new TreeNode(2);48         TreeNode t3 = new TreeNode(3);49         TreeNode t4 = new TreeNode(4);50         TreeNode t5 = new TreeNode(5);51         TreeNode t6 = new TreeNode(6);52         t3.setLeft(t2);53         t3.setRight(t1);54         t2.setLeft(t4);55         t2.setRight(t5);56         t1.setRight(t6);57         System.out.println(new TreeNodeNoneReverse().postorderTraversal(t3));58     }59 }60 　　
View Code

 


联系
我们