- 浏览: 184894 次
- 性别:
- 来自: 济南
文章分类
最新评论
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].
输出一颗树的后序遍历序列。我们可以用递归和迭代两种方法。用迭代时我们借助堆栈,因为是后序遍历,顺序为左-右-根,因此我们只需要通过根-右-左的顺序进行遍历,然后将序列翻转就可以了。代码如下:
递归:
迭代:
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [3,2,1].
输出一颗树的后序遍历序列。我们可以用递归和迭代两种方法。用迭代时我们借助堆栈,因为是后序遍历,顺序为左-右-根,因此我们只需要通过根-右-左的顺序进行遍历,然后将序列翻转就可以了。代码如下:
递归:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<Integer>(); if(root == null) return list; getPostorder(root, list); return list; } public void getPostorder(TreeNode root, List<Integer> list) { if(root == null) return; getPostorder(root.left, list); getPostorder(root.right, list); list.add(root.val); } }
迭代:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> postorderTraversal(TreeNode root) { LinkedList<Integer> list = new LinkedList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); if(root == null) return list; stack.add(root); while(!stack.isEmpty()) { TreeNode node = stack.pop(); list.addFirst(node.val); if(node.left != null) { stack.push(node.left); } if(node.right != null) { stack.push(node.right); } } return list; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 270Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 271You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 389Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 379Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 503Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 568Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 483Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 668Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 473The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 434Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 584Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 590Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 429All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 905Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 935Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 606Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 691Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 857Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 789You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 723For a undirected graph with tre ...
相关推荐
145.Binary_Tree_Postorder_Traversal二叉树的后序遍历【LeetCode单题讲解系列】
An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node ... Your task is to give the postorder traversal sequence of this tree.
python python_leetcode题解之145_Binary_Tree_Postorder_Traversal
144-Binary Tree Preorder Traversal94-Binary Tree Inorder Traversal145-Binary Tree Postorder Traversal(后续的非递归时间不够可以先跳过,有点难)层次遍历,队列辅助,相当于广搜。102-Binary Tree Level ...
javascript js_leetcode题解之145-binary-tree-postorder-traversal.js
在这个名为"Binary tree traversal.zip"的压缩包中,包含了作者在算法课上完成的一个关于二叉树遍历的作业。这个作业使用C++编程语言,并在Visual Studio 2019环境下编写。以下是关于二叉树遍历的详细知识: 1. **...
leetcode卡 LeetCode 记录一下再LeetCode上...Postorder Traversal], Tree/stack 2017.06.20 打卡[LeetCode 107. Binary Tree Level Order Traversal II], Tree/BFS 2017.06.20 打卡[LeetCode 324. Wiggle Sort II], S
`BinaryTree_PostOrder.java`可能包含了这种实现。递归版本会先遍历左子树,然后右子树,最后访问根节点。 4. **前序遍历(Preorder Traversal)** 前序遍历按照“根-左-右”的顺序访问节点,常用于复制整棵树或者...
- 后序遍历 (Postorder Traversal) - 层次遍历 (Level Order Traversal) ##### 2.2 进阶操作 - **查找**: 在二叉树中查找特定的节点。 - **插入**: 向二叉树中插入新的节点。 - **删除**: 从二叉树中删除特定的...
Binary Tree Postorder Traversal (145) 要求不用递归实现后序遍历 后序是left-right-root,那么首先用修正的前序root-right-left,然后reverse一下,变成left-right-root就行了,代码如下: Factorial Trailing ...
Javascript 的解决方案Leetcode Problems and interview problems in Javascript10 Regular ...Postorder Traversal.js107 Binary Tree Level Order Traversal II.js108 Convert Sorted Array to Binary Search Tr
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
主要有三种类型的遍历:前序遍历(Preorder Traversal)、后序遍历(Postorder Traversal)和中序遍历(Inorder Traversal)。前序遍历先访问根节点,再遍历左子树,最后遍历右子树;后序遍历则是先遍历左子树和右子...
在标签“BinaryTree”中,我们聚焦于二叉树相关的算法和数据结构。二叉树的其他遍历方法还包括前序遍历(Preorder Traversal,根-左-右)、中序遍历(Inorder Traversal,左-根-右)和后序遍历(Postorder Traversal...
9. **Binary Tree Postorder Traversal** (二叉树的后序遍历): 后序遍历有递归和迭代两种方法。在Java中,递归方法相对简单,先遍历左子树,再遍历右子树,最后访问根节点;迭代方法通常使用栈来模拟递归过程。 10....
递归是解决复杂问题的有效手段,例如"Binary Tree Postorder Traversal"(二叉树后序遍历)问题,可以通过递归实现。而回溯法常用于解决组合优化问题,如"Combination Sum"(组合求和),在Java中通常结合递归来实现...
在“Traverse binary tree”程序中,这四种遍历方法都被实现,允许用户根据需求选择合适的遍历策略。对于每种遍历方法,都需要设计一个适当的算法来正确地访问每个节点,并确保所有节点只被访问一次。 总结来说,...
然后,通过create_binary_tree函数手动创建了一个二叉树。最后,通过inorder_traversal、preorder_traversal和postorder_traversal函数实现了中序、先序和后序遍历。输出结果应该分别为:```pythonInorder Traversal...
3. **后序遍历(Postorder Traversal)** - **定义**:先遍历左子树,接着遍历右子树,最后访问根节点。 - **应用场景**:删除二叉树时,需要先删除叶子节点及其子树。 - **代码实现**: ```java public ...