当前位置:网站首页>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 .
边栏推荐
猜你喜欢
Vulnhub geminiinc V2
Is BigDecimal safe to calculate the amount? Look at these five pits~~
为什么我的mysql容器启动不了呢
OpenGL 索引缓存对象EBO和线宽模式
Symlink(): solution to protocol error in PHP artisan storage:link on win10
Wrong arrangement (lottery, email)
Basic knowledge of OpenGL (sort it out according to your own understanding)
Laravel time zone timezone
"Jianzhi offer 04" two-dimensional array search
XML (DTD, XML parsing, XML modeling)
随机推荐
previous permutation lintcode51
STL tutorial 8-map
Laravel time zone timezone
SystemVerilog -- OOP -- copy of object
Deploying WordPress instance tutorial under coreos
Shutter widget: centerslice attribute
Qt+vtk+occt reading iges/step model
vulnhub之GeminiInc v2
安装electron失败的解决办法
Pki/ca and digital certificate
temp
Solution à la défaillance de l'installation d'Electron
(construction notes) grasp learning experience
DEJA_VU3D - Cesium功能集 之 053-地下模式效果
Vulnhub narak
023(【模板】最小生成树)(最小生成树)
4000 word super detailed pointer
regular expression
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
Vulnhub's cereal