本文共 2044 字，大约阅读时间需要 6 分钟。

树 是一种经常用到的数据结构，用来模拟具有树状结构性质的数据集合。

树里的每一个节点有一个值和一个包含所有子节点的列表。从图的观点来看，树也可视为一个拥有N 个节点和N-1 条边的一个有向无环图。

二叉树是一种更为典型的树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。

树的遍历分为前序遍历、中序遍历、后序遍历。

                                                               图1

            图2

前序遍历：

首先访问根节点，然后遍历左子树，最后遍历右子树

图1：FBADCEGIH

图2：[1,2,3]

class Solution {    public List
   
     preorderTraversal(TreeNode root) {        List
    
      result = new ArrayList
     
      ();        Stack
      
        stack = new Stack
       
        ();        while(root != null || !stack.empty()){            if(root != null){                result.add(root.val);                stack.push(root);                root = root.left;            } else{                TreeNode tmp = stack.pop();                root = tmp.right;            }        }                return result;    }}
       
      
     
    
   

中序遍历：

先遍历左子树，然后访问根节点，然后遍历右子树。

通常来说，对于二叉搜索树，我们可以通过中序遍历得到一个递增的有序序列。

图1：ABCDEFGHI

图2：[1,3,2]

class Solution {    public List
   
     inorderTraversal(TreeNode root) {        List
    
      result = new ArrayList
     
      ();        Stack
      
        stack = new Stack
       
        ();        while(root != null || !stack.empty()){            if(root != null){                                stack.push(root);                root = root.left;            } else{                TreeNode tmp = stack.pop();                result.add(tmp.val);                root = tmp.right;            }        }          return result;      }}
       
      
     
    
   

后序遍历：

先遍历左子树，然后遍历右子树，最后访问树的根节点。

图1：ACEDBHIGF

图2：[3,2,1]

class Solution {    public List
   
     postorderTraversal(TreeNode root) {        List
    
      result = new ArrayList
     
      ();        if(root != null){            Stack
      
        stack = new Stack
       
        ();            Stack
        
          stack1 = new Stack
         
          (); stack.push(root); while(!stack.isEmpty()){ root = stack.pop(); stack1.push(root); if(root.left != null) stack.push(root.left); if(root.right != null) stack.push(root.right); } while(!stack1.isEmpty()){ result.add(stack1.pop().val); } } return result; }}
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/luxuiary/article/details/107783814 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！