算法跟练第十一弹——二叉树

跟着代码随想录刷题的第十一天。

代码随想录链接：代码随想录

part01 递归遍历

前序遍历：中左右
中序遍历：左中右
后序遍历：左右中

1.1 二叉树的前序遍历

题目链接：二叉树的前序遍历

代码：

/*** 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<>();pre(root,result);return result;}public void pre(TreeNode root,List<Integer>result){if(root==null){return;}result.add(root.val);pre(root.left,result);pre(root.right,result);}
}

1.2 二叉树的中序遍历

题目链接：二叉树的中序遍历

代码：

/*** 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<>();pre(root,result);return result;}public void pre(TreeNode root,List<Integer>result){if(root == null)return;pre(root.left,result);result.add(root.val);pre(root.right,result);}
}

1.3 二叉树的后序遍历

题目链接：二叉树的后序遍历

代码：

/*** 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<>();pre(root,result);return result;}public void pre(TreeNode root,List<Integer>result){if(root==null)return;pre(root.left,result);pre(root.right,result);result.add(root.val);}
}

part02 迭代遍历

2.1 二叉树的前序遍历

题目链接：二叉树的前序遍历

代码：

/*** 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<>();if(root==null)return result;stack.push(root);while(!stack.isEmpty()){TreeNode node = stack.peek();result.add(stack.pop().val);if(node.right!=null)stack.push(node.right);if(node.left!=null)stack.push(node.left);}return result;}
}

2.2 二叉树的中序遍历

题目链接：二叉树的中序遍历

代码：

/*** 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<>();if(root==null)return result;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while(cur!=null||!stack.isEmpty()){if(cur!=null){stack.push(cur);cur = cur.left;}else{cur = stack.pop();result.add(cur.val);cur = cur.right;}}return result;}
}

题解：主要是要考虑应该将左孩子全部入栈，再出栈，出栈时判断是否存在右孩子，存在就把指针指向右孩子

2.3 二叉树的后序遍历

题目链接：二叉树的后序遍历

代码：

/*** 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<>();if(root == null)return result;stack.push(root);while(!stack.isEmpty()){TreeNode node = stack.pop();result.add(node.val);if(node.left!=null)stack.push(node.left);if(node.right!=null)stack.push(node.right);}Collections.reverse(result);return result;}
}

题解：这次是利用链表的翻转，先中-右-左遍历，再翻转过来

part03 层序遍历

3.1 二叉树的层序遍历

题目链接：102.二叉树的层序遍历

代码：

/*** 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<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<List<Integer>>();if(root==null)return result;Queue<TreeNode> que = new LinkedList<>();int len = 0;que.add(root);while(!que.isEmpty()){len = que.size();List<Integer> q = new ArrayList<>();while(len>0){TreeNode cur = que.poll();if(cur.left!=null)que.add(cur.left);if(cur.right!=null)que.add(cur.right);q.add(cur.val);len--;}result.add(q);}return result;}
}

3.2 二叉树的层序遍历II

题目链接：102.二叉树的层序遍历II

代码：

/*** 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<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> result = new ArrayList<List<Integer>>();if(root==null)return result;Queue<TreeNode> que = new LinkedList<>();que.add(root);int len = 0;while(!que.isEmpty()){len = que.size();List<Integer> q = new ArrayList<>();while(len>0){TreeNode node = que.poll();if(node.left!=null)que.add(node.left);if(node.right!=null)que.add(node.right);q.add(node.val);len--;}result.add(q);}List<List<Integer>> list = new ArrayList<List<Integer>>();for(int i = result.size()-1;i>=0;i--){list.add(result.get(i));}return list;}
}

3.3 二叉树的右视图

题目链接：199.二叉树的右视图

代码：

/*** 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> rightSideView(TreeNode root) {List<Integer> result = new ArrayList<>();if(root==null)return result;Queue<TreeNode> que = new LinkedList<>();que.add(root);int len = 0;while(!que.isEmpty()){len = que.size();while(len>0){TreeNode node = que.poll();if(node.left!=null)que.add(node.left);if(node.right!=null)que.add(node.right);if(len==1)result.add(node.val);len--;}}return result;}
}

归纳

获取双重链表的第一层

result.get(i)