144.二叉树的前序遍历[https://leetcode.cn/problems/binary-tree-preorder-traversal/]
思路:栈实现的迭代遍历:出栈记录,右孩子非空右孩子进栈,左孩子非空左孩子进栈。
/**
* 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> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Stack<TreeNode> sc = new Stack<>();
sc.push(root);
TreeNode p;
while (!sc.isEmpty()) {
p = sc.pop();
ans.add(p.val);
if (p.right != null) {
sc.push(p.right);
}
if (p.left != null) {
sc.push(p.left);
}
}
return ans;
}
}
**-----------------------分割线-------------------------**
94.二叉树的中序遍历[https://leetcode.cn/problems/binary-tree-inorder-traversal/submissions/497799353/]
思路:栈实现的迭代遍历。我保持非空一路向左,否则出栈赋值右拐。
/**
* 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> inorderTraversal(TreeNode root) {
Stack<TreeNode> sc = new Stack<>();
List<Integer> ans = new ArrayList<>();
TreeNode p = root;
while(p!=null || !sc.isEmpty()){
if(p!=null){
sc.push(p);
p=p.left;
}else if(p==null){
p=sc.pop();
ans.add(p.val);
p=p.right;
}
}return ans;
}}
**-----------------------分割线-------------------------**
145.二叉树的后序遍历[https://leetcode.cn/problems/binary-tree-postorder-traversal/submissions/497800150/]
思路:二叉树的后序遍历,其实就是前序遍历的思路,当迭代遍历的前序遍历,将非空节点的左右节点进栈的顺序调换并且把结果数组reverse一下就是后序遍历结果。
/**
* 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> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Stack<TreeNode> sc = new Stack<>();
sc.push(root);
TreeNode p;
while (!sc.isEmpty()) {
p = sc.pop();
ans.add(p.val);
if (p.left != null) {
sc.push(p.left);
}
if (p.right != null) {
sc.push(p.right);
}
}
Collections.reverse(ans);
return ans;
}
}
-----真的理解为什么上述结果为什么就是后序遍历结果并不难,但是我们主动很难去想到,所以我选择死记。-----
标签:right,TreeNode,val,代码,随想录,ans,sc,第十二天,left
From: https://www.cnblogs.com/cssg/p/17983220