devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Day14--数据结构与算法(Java)二叉树的递归遍历和迭代遍历_java二叉树递归遍历,树节点的定义,树的构建,递归遍历

作者：你好赵伟 | 2024-03-20 15:54:01

赞

踩

java二叉树递归遍历,树节点的定义,树的构建,递归遍历

目录

一、二叉树的递归遍历

二叉树的定义 

前序遍历 

 中序遍历 

后序遍历

java中List的用法

二、二叉树的迭代遍历

前序遍历（用栈来模拟递归实现）

后序遍历 （在前序遍历的基础上调换左右顺序，再反转）

Java使用Collections.reverse()反转一个List

中序遍历 

三、统一迭代

一、二叉树的递归遍历

二叉树的定义 

  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. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public List<Integer> preorderTraversal(TreeNode root) {
  18.     LinkedList<Integer> result=new LinkedList<>();
  19.     preorder(root,result);
  20.     return result;
  21.     }
  22.     public void preorder(TreeNode root,LinkedList<Integer> result)
  23.     {
  24.     if(root==null)
  25.       {
  26.           return;
  27.       }
  28.     result.add(root.val);
  29.     preorder(root.left,result);
  30.     preorder(root.right,result);
  31.     }
  32. }

 中序遍历 

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public List<Integer> inorderTraversal(TreeNode root) {
  18.      List<Integer> result=new LinkedList<>();
  19.      inorder(root,result);
  20.      return result;
  21.     }
  22.     public void inorder(TreeNode root,List<Integer> result)
  23.     {
  24.       if(root==null)
  25.       {
  26.           return;
  27.       }
  28.       inorder(root.left,result);
  29.       result.add(root.val);
  30.       inorder(root.right,result);
  31.     }
  32. }

后序遍历

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public List<Integer> postorderTraversal(TreeNode root) {
  18.      List<Integer>result=new ArrayList<>();
  19.     postorder(root,result);
  20.     return result;
  21.     }
  22.     public void postorder(TreeNode root,List<Integer>result)
  23.     {
  24.         if(root==null)
  25.         return;
  26.         postorder(root.left,result);
  27.         postorder(root.right,result);
  28.         result.add(root.val);
  29.     }
  30. }

java中List的用法

List接口是Collection接口的子接口，List有一个重要的实现类--ArrayList类，List中的元素是有序排列的而且可重复，所以被称为是序列。

List可以精确的控制每个元素的插入位置，或删除某个位置元素，它的实现类ArrayList底层是由数组实现的。

List中有增删改查的方法。

所有已知实现类：

AbstractList ， AbstractSequentialList ， ArrayList ， AttributeList ， CopyOnWriteArrayList ， LinkedList ， RoleList ， RoleUnresolvedList ， Stack ， Vector

二、二叉树的迭代遍历

前序遍历（用栈来模拟递归实现）

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public List<Integer> preorderTraversal(TreeNode root) {
  18.      List<Integer> result = new ArrayList<>();
  19.         if (root == null){
  20.             return result;
  21.         }
  22.         Stack<TreeNode> stack = new Stack<>();
  23.         stack.push(root);
  24.         while (!stack.isEmpty()){
  25.             TreeNode node = stack.pop();
  26.             result.add(node.val);
  27.             if (node.right != null){
  28.                 stack.push(node.right);
  29.             }
  30.             if (node.left != null){
  31.                 stack.push(node.left);
  32.             }
  33.         }
  34.         return result;
  35.     }
  36. }

后序遍历 （在前序遍历的基础上调换左右顺序，再反转）

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public List<Integer> postorderTraversal(TreeNode root) {
  18.      List<Integer> result=new ArrayList<>();
  19.      if(root==null)
  20.      {
  21.          return result;
  22.      }
  23.      Stack<TreeNode>stack=new Stack<>();
  24.      stack.push(root);
  25.      while(!stack.isEmpty())
  26.      {
  27.          TreeNode node=stack.pop();
  28.          result.add(node.val);
  29.          if(node.left!=null)
  30.          {
  31.             stack.push(node.left);
  32.          }
  33.          if(node.right!=null)
  34.          {
  35.              stack.push(node.right);
  36.          }
  37.      }
  38.     Collections.reverse(result);
  39.     return result;
  40.     }
  41. }

 

 

Java使用Collections.reverse()反转一个List

中序遍历 

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public List<Integer> inorderTraversal(TreeNode root) {
  18.       List<Integer>result=new ArrayList<>();
  19.       if(root==null)
  20.       {
  21.           return result;
  22.       }
  23.       Stack<TreeNode>stack=new Stack<>();
  24.       TreeNode cur=root;
  25.       while(cur!=null||!stack.isEmpty())
  26.       {
  27.           if(cur!=null)
  28.           {
  29.               stack.push(cur);
  30.               cur=cur.left;
  31.           }
  32.           else
  33.           {
  34.               cur=stack.pop();
  35.               result.add(cur.val);
  36.               cur=cur.right;
  37.           }
  38.       }
  39.       return result;
  40.     }
  41. }

只要不是空结点，就一路向左入栈，是空结点，就弹出当前结点，并且放入返回结果中。继续判断右节点是不是为空，如果为空，就继续弹出刚刚访问过的结点。 在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

三、统一迭代

代码随想录

二刷的时候再看

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/274818
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号