二叉树:
种类:满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树
存储方式:链式存储、线式存储(顺序存储)
二叉数遍历:深度优先搜索(前序、中序、后序):使用递归实现(实际用栈来实现)、迭代法(非递归的方式、栈),广度优先搜索(层序遍历):用队列
递归三步走写法:1、确定递归函数的参数和返回值。2、确定终止条件。3、确定单层递归的逻辑。
144、二叉树的前序遍历
/**
* 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<>();
// preorder(root, result);
// return result;
// }
// public void preorder(TreeNode root, List<Integer> result){
// if(root == null){
// return;
// }
// result.add(root.val);
// preorder(root.left, result);
// preorder(root.right, result);
// }
// 方法二:非递归的方法
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
if(cur != null){
result.add(cur.val);
stack.push(cur.right);
stack.push(cur.left);
}else{
continue;
}
}
return result;
}
// 方法三:统一风格的非递归
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root != null){
stack.push(root);
}
while(!stack.isEmpty()){
if(stack.peek() != null){
TreeNode cur = stack.pop();
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
stack.push(cur);
stack.push(null);
}else{
stack.pop();
TreeNode cur = stack.pop();
result.add(cur.val);
}
}
return result;
}
}
145、二叉树的后序遍历
/**
* 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<>();
// postOrder(root, result);
// return result;
// }
// public void postOrder(TreeNode root, List<Integer> result){
// if(root == null){
// return;
// }
// postOrder(root.left, result);
// postOrder(root.right, result);
// result.add(root.val);
// }
// 方法二:非递归
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if(root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
result.add(cur.val);
if(cur.left != null){
stack.push(cur.left);
}
if(cur.right != null){
stack.push(cur.right);
}
}
Collections.reverse(result);
return result;
}
// 方法三:统一风格的非递归
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root != null){
stack.push(root);
}
while(!stack.isEmpty()){
if(stack.peek() != null){
TreeNode cur = stack.pop();
stack.push(cur);
sta