当前位置:网站首页>145. Post order traversal of binary tree
145. Post order traversal of binary tree
2022-07-03 12:12:00 【zwanying】
The traversal of the tree :
1、 breadth-first level Use the iterative method .
2、 Depth first Before the order , Middle preface , In the following order , Refers to the order of root nodes use recursive , Iterative implementation .
Three elements of recursion :
1、 Parameters , Return value
2、 Termination conditions
3、 Every recursive logic
Recursive implementation
Before the order , Middle preface , Post sequence similar , Only the subsequent implementation is shown here .
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList();
digui(root,list);
return list;
}
public void digui(TreeNode r ,List<Integer> list){
if(r == null) return ;
// Right and left
digui(r.left,list);
digui(r.right,list);
list.add(r.val);
}
}
Iterative method
iteration , Implementation with stack .
The element to be output is out of the stack , Iterated element stack .
Iterative implementation
Preamble implementation
Press the right node first , Press the left node again , Make sure the output sequence is left first and then right .
Pay attention : Null pointers do not need to be stacked .
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
// Iterative method
if(root == null) return list;
Stack<TreeNode> stack = new Stack();
stack.push(root);
while(!stack.isEmpty()){
TreeNode t = stack.pop();
list.add(t.val);
if(t.right != null) stack.push(t.right);
if(t.left != null) stack.push(t.left);
}
return list;
}
}
tip :
Note that the boundary value is empty .
In order to achieve
First traverse the left node , Pressing stack .
There is no left node , Out of the stack , Output .
Then traverse the right node , Pressing stack .
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
// In order to arrange Left in Right
List<Integer> list = new ArrayList<>();
TreeNode cur = root;
Stack<TreeNode> stack = new Stack<>();
if(root == null) return list;
while(!stack.isEmpty() || cur!=null){
if(cur!=null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
}
return list;
}
}
Subsequent implementation
Before the order Around the middle In the following order Right and left
To achieve Center right left , And then reverse , Achieve left and right .
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
// in , Right , Left
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root == null) return list;
stack.push(root);
while(!stack.isEmpty()){
TreeNode r = stack.pop();
list.add(r.val);
if(r.left != null) stack.push(r.left);
if(r.right != null) stack.push(r.right);
}
Collections.reverse(list);
return list;
}
}
Implementation of unified iterative method
The reasons for the inconsistency in the previous text :
Order of access , It is inconsistent with the order of traversing the returned results .
solve : If it is an element to traverse the result , The stack is followed by a null pointer to identify .
Preorder traversal is implemented as follows , In the sequence traversal , After the sequence traversal , Just fine tune the order .
The former sequence traversal : Around the middle . Stack order : Right , Left , in ( Processing elements , Followed by null identification )
In the sequence traversal : Left middle right . Stack order : Right , in ( Heel null identification ), Left
After the sequence traversal : Right and left . Deposit sequence : in ( Heel null identification ), Right , Left
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode t = stack.peek();
if(t == null){
stack.pop();
list.add(stack.pop().val);
}else{
stack.pop();
if(t.right != null) stack.push(t.right);
if(t.left != null) stack.push(t.left);
stack.push(t);
stack.push(null);
}
}
return list;
}
}
Pay attention to mistakes :
1、 The method to get the top element of the stack :peek()
2、 Remember to traverse every node , First out of the stack , Go back to the stack . Don't just get in and out , Operation exceeded expectations .
边栏推荐
- Slf4j log facade
- ES6 standard
- vulnhub之Ripper
- Dart: about grpc (I)
- Go language to realize static server
- Socket TCP for network communication (I)
- Ripper of vulnhub
- regular expression
- DNS multi-point deployment IP anycast+bgp actual combat analysis
- win10 上PHP artisan storage:link 出现 symlink (): Protocol error的解决办法
猜你喜欢
AOSP ~ NTP (Network Time Protocol)
Socket TCP for network communication (I)
Php Export word method (One MHT)
Summary of development issues
Raven2 of vulnhub
Xiaopeng P7 hit the guardrail and the airbag did not pop up. The official responded that the impact strength did not meet the ejection requirements
Fluent: Engine Architecture
4000字超详解指针
Download address and installation tutorial of vs2015
Introduction to the implementation principle of rxjs observable filter operator
随机推荐
【附下载】密码获取工具LaZagne安装及使用
Master and backup role election strategy in kept
(construction notes) learn the specific technology of how to design reusable software entities from three levels: class, API and framework
STL tutorial 8-map
php 获取文件夹下面的文件列表和文件夹列表
Vulnhub's Tomato (tomato)
ES6新特性
Flutter 退出登录二次确认怎么做才更优雅?
LeetCode 0556.下一个更大元素 III - 4步讲完
836. Merge sets (day 63) and search sets
MySQL searches and sorts out common methods according to time
Capturing and sorting out external Fiddler -- Conversation bar and filter [2]
Cacti monitors redis implementation process
在网上炒股开户可以吗?资金安全吗?
OpenGL 着色器使用
Php Export word method (One MHT)
PHP導出word方法(一mht)
PHP导出word方法(一phpword)
Summary of development issues
OpenGL 绘制彩色的三角形