一、144. 二叉树的前序遍历
题目连接：https://leetcode.cn/problems/binary-tree-preorder-traversal/
思路一、递归方法
1、定义递归终止条件 if (root == null) return;
2、递归方法体：前序遍历：先中间root.val 添加到list，在左边、在右边
/**
* 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 {
private void preorderTraversal(TreeNode root, List<Integer> list) {
if (root == null) return;
list.add(root.val);
preorderTraversal(root.left, list);
preorderTraversal(root.right, list);
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
preorderTraversal(root, result);
return result;
}
}
思路二、使用迭代法,使用stack,先放入right,再放入left,在弹出left,依次循环
第一种写法：
/**
* 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> result = new ArrayList<>();
if (root != null) {
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode treeNode = stack.pop();
result.add(treeNode.val);
if (treeNode.right != null) stack.push(treeNode.right);
if (treeNode.left != null) stack.push(treeNode.left);
}
}
return result;
}
}
第二种写法
/**
* 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> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()){
if (cur != null) {
result.add(cur.val);
stack.push(cur);
cur = cur.left;
} else {
TreeNode treeNode = stack.pop();
cur = treeNode.right;
}
}
return result;
}
}
二、94. 二叉树的中序遍历
题目连接：https://leetcode.cn/problems/binary-tree-inorder-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 {
private void inorderTraversal(TreeNode root, List<Integer> list) {
if (root == null) return;
inorderTraversal(root.left, list);
list.add(root.val);
inorderTraversal(root.right, list);
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderTraversal(root, result);
return result;
}
}
思路二、迭代法,一路向走，遇到left是空的，看这个节点的右节点，右节点是空的话看栈顶的元素
/**
* 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) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()){
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
TreeNode treeNode = stack.pop();
result.add(treeNode.val);
cur = treeNode.right;
}
}
return result;
}
}
三、145. 二叉树的后序遍历
题目连接：https://leetcode.cn/problems/binary-tree-postorder-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 {
private void postorderTraversal(TreeNode root, List<Integer> list) {
if (root == null) return;
postorderTraversal(root.left, list);
postorderTraversal(root.right, list);
list.add(root.val);
}
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
postorderTraversal(root, result);
return result;
}
}
思路二迭代法
方法一、使用前序方式 中右左遍历，最后倒序，就得到左右中
/**
* 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> result = new ArrayList<>();
if (root != null) {
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode treeNode = stack.pop();
result.add(treeNode.val);
if (treeNode.left != null) stack.push(treeNode.left);
if (treeNode.right != null) stack.push(treeNode.right);
}
}
int left = 0;
int right = result.size() - 1;
while (left < right) {
int temp = result.get(left);
result.set(left, result.get(right));
result.set(right, temp);
left++;
right--;
}
return result;
}
}
方法二、访问到中间节点的时候，看它的右节点是否为空，如果为空则直接弹出。
如果不为空并且没有遍历过右节点，则遍历右节点，遍历过右节点后，最后遍历中节点
/**
* 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> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode pre = null;
while (cur != null || !stack.isEmpty()){
if (cur != null){
stack.push(cur);
cur = cur.left;
} else {
TreeNode treeNode = stack.peek();
//当右节点是空或者右节点访问过了，中间的节点可以弹出了
if (treeNode.right == null || treeNode.right == pre) {
stack.pop();
result.add(treeNode.val);
pre = treeNode;
cur = null;
} else {
cur = treeNode.right;
}
}
}
return result;
}
}
网友评论