二叉树前中后层序遍历方法(Java版)

二叉树前中后层序遍历方法(Java版)

二叉树的节点如下所示:

 1 public class TreeNode {
 2      int val;
 3      TreeNode left;
 4      TreeNode right;
 5      TreeNode() {}
 6      TreeNode(int val) { this.val = val; }
 7      TreeNode(int val, TreeNode left, TreeNode right) {
 8        this.val = val;
 9        this.left = left;
10        this.right = right;
11      }
12 }

 

1 二叉树前序遍历

前序遍历的遍历顺序是:中左右。Leetcode对应题目为144. 二叉树的前序遍历

下图二叉树的前序遍历为:ABDGCEFH

二叉树前中后层序遍历方法(Java版)

 

1.1 递归

 1 class Solution {
 2     public List<Integer> preorderTraversal(TreeNode root) {
 3         List<Integer> list = new ArrayList<>();
 4         traversal(root,list);
 5         return list;
 6     }
 7 
 8     void traversal(TreeNode root,List<Integer> list){
 9         if(root==null) return;
10     //先访问当前节点
11         list.add(root.val);
12     //遍历左孩子
13         traversal(root.left,list);
14         //再遍历右孩子
15         traversal(root.right,list);
16     }
17 }

 

1.2 迭代

 1 class Solution {
 2     public List<Integer> preorderTraversal(TreeNode root) {
 3     //保存节点值
 4         List<Integer> list = new ArrayList<>();
 5     //保存访问过的节点
 6         Stack<TreeNode> stack = new Stack<>();
 7         TreeNode p = root;
 8         while(p!=null || !stack.empty()){
 9             if(p!=null){
10                 list.add(p.val);
11         //将当前节点入栈
12                 stack.push(p);
13         //访问左孩子
14                 p=p.left;
15             }else{
16         //出栈最近访问的节点,并访问其右孩子
17                 p=stack.pop();
18                 p=p.right;
19             }
20         }
21         return list;
22     }
23 }

 

2 二叉树中序遍历

中序遍历的遍历顺序是:左中右。Leetcode对应题目为94. 二叉树的中序遍历

下图二叉树的中序遍历为:DGBAECHF

二叉树前中后层序遍历方法(Java版)

 

2.1 递归

 1 class Solution {
 2     public List<Integer> inorderTraversal(TreeNode root) {
 3         List<Integer> list = new ArrayList<>();
 4         traversal(root,list);
 5         return list;
 6     }
 7 
 8     void traversal(TreeNode root,List<Integer> list){
 9         if(root==null) return;
10         traversal(root.left,list);
11         list.add(root.val);
12         traversal(root.right,list);
13     }
14 }

 

2.2 迭代

 1 class Solution {
 2     public List<Integer> inorderTraversal(TreeNode root) {
 3         List<Integer> list = new ArrayList<>();
 4         Stack<TreeNode> stack = new Stack<>();
 5         TreeNode p = root;
 6         while(p!=null || !stack.empty()){
 7             if(p!=null){
 8         //先不断遍历左孩子,将左孩子入栈
 9                 stack.push(p);
10                 p=p.left;
11             }else{
12         //左孩子为空或遍历完成后,就将父节点出栈并遍历,再访问右孩子
13                 p = stack.pop();
14                 list.add(p.val);
15                 p=p.right;
16             }
17         }
18         return list;
19     }
20 }

 

3 二叉树后序遍历

后序遍历的遍历顺序是:左右中。Leetcode对应题目为145. 二叉树的后序遍历

下图二叉树的后序遍历为:GDBEHFCA

二叉树前中后层序遍历方法(Java版)

 

3.1 递归

 1 class Solution {
 2     public List<Integer> postorderTraversal(TreeNode root) {
 3         List<Integer> list = new ArrayList<>();
 4         traversal(root,list);
 5         return list;
 6     }
 7 
 8     void traversal(TreeNode root,List<Integer> list){
 9         if(root==null) return;
10         traversal(root.left,list);
11         traversal(root.right,list);
12         list.add(root.val);
13     }
14 }

 

3.2 迭代

技巧法—该迭代方法,在前序遍历的迭代方法上稍作了修改。前序遍历时先访问父节点,再访问左孩子,最后访问右孩子,形成中左右的遍历顺序。在这里,先访问父节点,再访问右孩子,最后访问左孩子,形成中右左的遍历顺序。而我们知道右序遍历的遍历顺序是左右中,我们把上面得到的结果反转不就得到后序遍历的结果了。

 1 class Solution {
 2     public List<Integer> postorderTraversal(TreeNode root) {
 3         List<Integer> list = new ArrayList<>();
 4         Stack<TreeNode> stack = new Stack<>();
 5         TreeNode p = root;
 6         while(p!=null || !stack.empty()){
 7             if(p!=null){
 8                 list.add(p.val);
 9                 stack.push(p);
10                 p = p.right;
11             }else{
12                 p = stack.pop();
13                 p = p.left;
14             }
15         }
16     //将list中的结果反转
17         Collections.reverse(list);
18         return list;
19     }
20 }

 

常规法—后序遍历需要确定是从左子树回到父节点,还是从右子树回到父节点。如果从左子树回到父节点,则需要先遍历右子树;如果从右子树回到父节点,则访问父节点。在这里,用节点pre标记前一个访问的节点,用node标记当前要处理的节点,当node的右子树非空且不是前一个访问的节点(pre)时,先访问node的右子树,否则访问node节点。

 1 class Solution {
 2     public List<Integer> postorderTraversal(TreeNode root) {
 3         List<Integer> list = new ArrayList<>();
 4         Stack<TreeNode> stack = new Stack<>();
 5         TreeNode pre = null;
 6         while(root!=null || !stack.isEmpty()){
 7             //先遍历左子树
 8             while (root != null) {
 9                 stack.push(root);
10                 root = root.left;
11             }
12             TreeNode node = stack.pop();
13             //当右子树非空,同时右子树还没访问时,先访问右子树
14             if (node.right != null && node.right != pre) {
15                 root = node.right;
16                 stack.push(node);
17             }else{
18                 //该节点的右子树为空或已访问后,就访问该节点
19                 list.add(node.val);
20                 pre = node;
21             }
22         }
23         return list;
24     }
25 }

 

4 二叉树层序遍历

层序遍历的遍历顺序是:从左至右一层层访问。Leetcode对应题目为102. 二叉树的层序遍历

下图二叉树的层序遍历为:ABCDEFGH

二叉树前中后层序遍历方法(Java版)

 

4.1 递归

 1 class Solution {
 2 
 3     List<List<Integer>> reList = new ArrayList<>();
 4 
 5     public List<List<Integer>> levelOrder(TreeNode root) {
 6         traversal(root,0);
 7         return reList;
 8     }
 9 
10     void traversal(TreeNode root,int deep){
11         if(root==null) return;
12         deep++;
13         if(reList.size()<deep){
14             //当层级增加时,list的Item也增加,利用list的索引值进行层级界定
15             List<Integer> item = new ArrayList<>();
16             reList.add(item);
17         }
18         reList.get(deep-1).add(root.val);
19         traversal(root.left,deep);
20         traversal(root.right,deep);
21     }
22 }

 

4.2 迭代

 1 class Solution {
 2     public List<List<Integer>> levelOrder(TreeNode root) {
 3         List<List<Integer>> reList = new ArrayList<>();
 4         if(root==null) return reList;
 5         Queue<TreeNode> queue = new LinkedList<>();
 6         queue.offer(root);
 7         while(!queue.isEmpty()){
 8             List<Integer> item = new ArrayList<>();
 9             //len保存每层的节点数
10             int len = queue.size();
11             while(len>0){
12                 TreeNode p = queue.poll();
13                 item.add(p.val);
14                 if(p.left!=null) queue.offer(p.left);
15                 if(p.right!=null) queue.offer(p.right);
16                 len--;
17             }
18             reList.add(item);
19         }
20         return reList;
21     }
22 }

 

 

 

上一篇:lens 添加 k8s 集群


下一篇:Kubernetes 集群日志 和 EFK 架构日志方案 (转)