- 浏览: 173907 次
- 性别:
- 来自: 济南
文章分类
最新评论
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 227Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 229You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 343Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 335Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 452Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 514Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 431Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 622Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 429The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 388Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 520Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 534Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 371All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 862Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 883Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 557Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 602Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 766Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 737You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 631For 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.
144-Binary Tree Preorder Traversal94-Binary Tree Inorder Traversal145-Binary Tree Postorder Traversal(后续的非递归时间不够可以先跳过,有点难)层次遍历,队列辅助,相当于广搜。102-Binary Tree Level ...
Construct Binary Tree from Inorder and Postorder Traversal 二叉查找树 Unique Binary Search Trees Unique Binary Search Trees II Validate Binary Search Tree Convert Sorted Array to Binary Search Tree ...
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
Binary Tree Postorder Traversal (145) 要求不用递归实现后序遍历 后序是left-right-root,那么首先用修正的前序root-right-left,然后reverse一下,变成left-right-root就行了,代码如下: Factorial Trailing ...
* [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]...
LeetCodeLeetCode solutions(Java)树Minimum Depth of Binary Tree栈evaluate-reverse-polish-notation穷举max-points-on-a-line链表sort-list排序insertion-sort-list树binary-tree-postorder-traversal树binary-...
binary-tree-postorder-traversal 树 binary-tree-preorder-traversal 链表 linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-...
java lru leetcode ...Tree/BinaryTree BST HashTable Disjoint Set Trie BloomFilter LRU Cache Algorithm General Coding InOrder/PreOrder/PostOrder Traversal Greedy Recursion/Backtrace Breadth-fi
lru缓存leetcode LeetCode_Note leetcode 个人笔记 ...[106_construct-binary-tree-from-inorder-and-postorder-traversal.cpp] [107_binary-tree-level-order-traversal-ii.cpp] [108_convert-sorted
106.construct-binary-tree-from-inorder-and-postorder-traversal (从中序与后序遍历序列构造二叉树) 112.path-sum (路径总和) 116.populating-next-right-pointers-in-each-node (填充每个节点的下一个右侧节点
2. Depth First Traversal(Pre-order,Post-order,In-order) 您可以在此处了解有关这些算法的更多信息: 运行项目 1. Clone the repo. 2. Install dependencies using `npm install` or `yarn install`. 3. Run the ...
leetcode 跳跃 Algorithm 算法题解: 包括书籍算法, 程序员算法面试指南, 还有leetcode算法题 ...construct-binary-tree-from-inorder-and-postorder-traversal 无官方题解 116 populating-next-right-pointers-in-eac
cout<<" traversal in postorder ... 后序遍历二叉树"; cout<<" traversal in levelorder ... 广度优先遍历二叉树"; cout求某结点的双亲"; cout<<" calculate the depth of the tree ... 求该树的深度"; ...
Leetcode问题用JavaScript解决使用...二叉树后置遍历( https://leetcode.com/problems/binary-tree-postorder-traversal/ ) Node.js样式标准代码应遵循Node.js样式标准( https://github.com/felixge/node-style-gu
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ 2 题目描述 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 中序...
poj与leetcode 自述文件 介绍 本repo由鞠承佑、钟恺健、王少泽创建。 它在帐户SuanFaRuoji(算法弱鸡)下...└──889_construct_binary_tree_from_preorder_and_postorder_traversal └──zkj_python.py 我们的任务
3.6 Finding the smallest and largest values in the binary search tree 25 3.7 Tree Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.7.1 Preorder . . . . . . . . . . . . . . . . ....