给定一个二叉树,返回他的后序遍历的序列。
后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。
数据范围:二叉树的节点数量满足 ,二叉树节点的值满足 ,树的各节点的值各不相同
样例图
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型一维数组 */ public int[] postorderTraversal (TreeNode root) { // write code here if(root == null) return new int[0]; Stack<TreeNode> stack1 = new Stack<>(); Stack<TreeNode> stack2 = new Stack<>(); stack1.push(root); while(!stack1.isEmpty()){ TreeNode node = stack1.pop(); stack2.push(node); if(node.left != null) stack1.push(node.left); if(node.right != null) stack1.push(node.right); } int[] postOrderSeq = new int[stack2.size()]; int idx = 0; while(!stack2.isEmpty()) postOrderSeq[idx ++] = stack2.pop().val; return postOrderSeq; } }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型vector */ vector<int> res; vector<int> postorderTraversal(TreeNode* root) { if(root ==nullptr)return res; postorderTraversal(root->left); postorderTraversal(root->right); res.push_back(root->val); return res; } };
func postorderTraversal(root *TreeNode) []int { res := make([]int, 0) cur, mostRight := root, &TreeNode{} for cur != nil { mostRight = cur.Left if mostRight != nil { for mostRight.Right != nil && mostRight.Right != cur { mostRight = mostRight.Right } if mostRight.Right != cur { mostRight.Right = cur cur = cur.Left continue } else { mostRight.Right = nil rN := reverseRight(cur.Left) cpRn := rN for rN != nil { res = append(res, rN.Val) rN = rN.Right } reverseRight(cpRn) } } cur = cur.Right } rN := reverseRight(root) cpRn := rN for rN != nil { res = append(res, rN.Val) rN = rN.Right } reverseRight(cpRn) return res } func reverseRight(root *TreeNode) *TreeNode { var pre *TreeNode for root != nil { cur := root root = root.Right cur.Right = pre pre = cur } return pre }
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型一维数组 */ public int[] postorderTraversal (TreeNode root) { // 后序遍历: left -> right -> this // 存储后序遍历的结果 List<Integer> arrayList = new ArrayList(); // 后序遍历 postDFS(root, arrayList); // 转int数组 return arrayList.stream().mapToInt(i->i).toArray(); } public void postDFS (TreeNode root, List<Integer> arrayList) { // 节点空,返回 if(root == null){ return; } // 向左遍历 postDFS (root.left, arrayList); // 向右遍历 postDFS (root.right, arrayList); // 存储当前节点 arrayList.add(root.val); } }
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { private List<Integer> list = new ArrayList(); /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型一维数组 */ public int[] postorderTraversal (TreeNode root) { // write code here Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while(!stack.isEmpty() || cur != null) { if(cur!=null) { list.add(cur.val); stack.push(cur); cur = cur.right; } else{ cur = stack.pop(); cur = cur.left; } } int len = list.size(); int[] result = new int[len]; for (int i = 0; i < list.size(); i++) { result[i] = list.get(len -i-1); } return result; } }
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型一维数组 */ ArrayList<Integer> integers = new ArrayList<Integer>(); public int[] postorderTraversal (TreeNode root) { // write code here tran(root); int[] result = new int[integers.size()]; for (int i = 0; i < integers.size(); i++) { result[i] = integers.get(i); } return result; } public void tran(TreeNode node) { if (node != null) { tran(node.left); tran(node.right); integers.add(node.val); } } }
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型vector */ vector<int> postorderTraversal(TreeNode* root) { if (root) { postorderTraversal(root->left); postorderTraversal(root->right); postorder.push_back(root->val); } return postorder; } private: vector<int>postorder; };
void postorderTraver(struct TreeNode* root, int* res, int* StaticReturnSize ) { if(root->left!=NULL) postorderTraver(root->left, res, StaticReturnSize); if(root->right!=NULL) postorderTraver(root->right, res, StaticReturnSize); res[(*StaticReturnSize)++] = root->val; } int* postorderTraversal(struct TreeNode* root, int* returnSize ) { static int res[1000]={0}, StaticReturnSize=0; if(root==NULL) return NULL; postorderTraver(root, res, &StaticReturnSize); *returnSize = StaticReturnSize; return res; }
void postOrder(struct TreeNode* root, int** a, int* count) { if (root != NULL) { postOrder(root->left, a, count); postOrder(root->right, a, count); (*a)[(*count)++] = root->val; } } int* postorderTraversal(struct TreeNode* root, int* returnSize) { int* a = malloc(sizeof(int) * 1001); int count = 0; postOrder(root, &a, &count); *returnSize = count; int* result = malloc(sizeof(int) * count); memcpy(result, a, sizeof(int) * count); free(a); return result; }
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型一维数组 */ public int[] postorderTraversal (TreeNode root) { // write code here List<Integer> list = new ArrayList<>(); preOrder(root,list); return list.stream().mapToInt(i->i).toArray(); } private void preOrder(TreeNode node,List<Integer> list){ if(node == null){ return; } preOrder(node.left,list); preOrder(node.right,list); list.add(node.val); } }
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型一维数组 */ public int[] postorderTraversal (TreeNode root) { // write code here if (null == root) { return new int[] {}; } Stack<TreeNode> stack = new Stack<>(); List<Integer> nums = new ArrayList<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode top = stack.pop(); nums.add(0, top.val); if (top.left != null) { stack.push(top.left); } if (top.right != null) { stack.push(top.right); } } return list2Array(nums); } /** * List<Integer>转化为int[] * * * @param nums List<Integer>类 * @return int整型一维数组 */ public int[] list2Array(List<Integer> nums) { int[] numArray = new int[nums.size()]; for (int i = 0; i < nums.size(); i++) { numArray[i] = nums.get(i); } return numArray; } }
int count=0; int arr[101]; void postOrder(struct TreeNode*root,int*arr) { if(root) { postOrder(root->left,arr); postOrder(root->right,arr); arr[count++]=root->val; } } int* postorderTraversal(struct TreeNode* root, int* returnSize ) { // write code here postOrder(root,arr); *returnSize=count; return arr; }方法二:栈
struct TreeNode*stack[100]; int arr[101]; int count=0; int top=-1; //记录上一个访问的节点 struct TreeNode* prev = NULL; //入栈 void push(struct TreeNode*node) { stack[++top]=node; } //出栈 struct TreeNode* pop(void) { return stack[top--]; } //后序遍历 左->右->根 //用栈实现,先进后出 int* postorderTraversal(struct TreeNode* root, int* returnSize ) { // write code here if(!root) { *returnSize=0; return NULL; } while(root||top!=-1) { while(root) { push(root); root=root->left; } root=stack[top]; //如果栈顶元素的右节点为空或者已经访问过,则可以访问根节点 if (!root->right || root->right == prev) { //根节点存在,保存val arr[count++] = root->val; //记录上一个访问的节点 prev = root; //栈顶元素出栈 root = pop(); //将根节点置为NULL,避免再次访问 root = NULL; } else { //开始遍历右节点 root = root->right; } } *returnSize=count; return arr; }
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型vector */ vector<int> postorderTraversal(TreeNode* root) { // write code here stack<TreeNode*> st; vector<int> vec; TreeNode *node = root, *stTop; if (root != nullptr) { st.push(root); } while (!st.empty()) { stTop = st.top(); if (stTop->right == node || (stTop->right == nullptr && stTop->left == node) || (stTop->left == nullptr && stTop->right == nullptr)) { st.pop(); node = stTop; vec.push_back(node->val); } else { if (stTop->right != nullptr) { st.push(stTop->right); } if (stTop->left != nullptr) { st.push(stTop->left); } } } return vec; } };