二叉树的遍历(包含非递归实现)

一、基本遍历规则

给出一个二叉树如下图所示。

二叉树.PNG

前序遍历首先访问根节点，然后遍历左子树，最后右子树。前序遍历结果为：F B A D C E G I H
中序遍历首先遍历左子树，然后访问根节点，最后右子树。中序遍历结果为：A B C D E F G H I
后序遍历首先遍历左子树，然后遍历右子树，最后根节点。后序遍历结果为：A C E D B H I G F
层次遍历故名思意就是按照二叉树的层次关系，逐层进行访问。层次遍历结果为：F B G A D I C E H

首先定义树的数据结构如下

  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }

二、前序遍历实现

递归实现
递归思路很简单，按前序遍历的规则即可，先访问根节点，然后递归访问左子树，最后递归访问右子树，递归返回条件为当前节点为空。

List<Integer> res = new ArrayList<>();
public void preorderTraversal(TreeNode root){    
    if(node == null) return;
    res.add(node.val); 
    preorderTraversal(node.left); 
    preorderTraversal(node.right);
}

非递归实现
非递归实现较递归略复杂，主要思路是借助栈来记录运行过程中的节点。在迭代时首先访问根节点，由于栈具有先进后出的特点，故先将右孩子入栈，最后将左孩子入栈，这样在下次迭代时，左孩子首先被弹出，其次是右孩子，满足前序遍历的规律。

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        if(root == null) return list;
        stack.add(root);
        while(!stack.isEmpty()){
            TreeNode temp = stack.pollLast();
            list.add(temp.val);
            if(temp.right != null){
                stack.add(temp.right);
            }
            if(temp.left != null){
                stack.add(temp.left);
            }
        }
        return list;
    }

三、后序遍历实现

递归实现
递归思路同上，不在累述。

List<Integer> res = new ArrayList<>();
public void preorderTraversal(TreeNode root){    
    if(node == null) return; 
    preorderTraversal(node.left); 
    preorderTraversal(node.right);
    res.add(node.val);
}

非递归实现
后序遍历的迭代方法实现可以类比前序遍历。首先我们知道前序遍历的遍历顺序为中左右，而后序遍历的顺序为左右中，中左右到左右中的可以由下图变换获取：

中序转后序.png

所以只需在前序遍历的代码上略做改动即可

public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> list = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root == null)return list;
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.addFirst(node.val);//头插法，相当于翻转结果
            
            //调整入栈顺序，先压左子树后压右子树
            if(node.left != null)stack.push(node.left);
            if(node.right != null) stack.push(node.right);
        }
        return list;
    }

四、中序遍历

递归实现
思路同上。

List<Integer> res = new ArrayList<>();
public void preorderTraversal(TreeNode root){    
    if(node == null) return; 
    preorderTraversal(node.left); 
    res.add(node.val);
    preorderTraversal(node.right);
}

非递归实现
按中序遍历顺序，每到一个节点A,因为根的访问在中间，所以先将A入栈。然后遍历左子树，接着访问 A,最后遍历右子树。在访问完A后，A就可以出栈了。

    public List < Integer > inorderTraversal(TreeNode root) {
        List < Integer > res = new ArrayList < > ();
        Stack < TreeNode > stack = new Stack < > ();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }
        return res;
    }

最后编辑于：2020.09.04 22:34:45