算法-二叉树遍历

末蓝、 2024-04-18 10:32 37阅读 0赞

#### 文章目录 ####

*  1. 二叉树遍历
 *  2. 二叉树遍历的实现
 *   *   *  2.1 先序遍历
         *   *  2.1.1 非递归实现
             *  2.1.2 递归实现
         *  2.2 中序遍历
         *   *  2.2.1 非递归实现
             *  2.2.2 递归实现
         *  2.3 后序遍历
         *   *  2.3.1 非递归实现
             *  2.3.2 递归实现

## 1. 二叉树遍历 ##

二叉树遍历的递归方式非常简单，非递归方式则相对复杂。通常二叉树节点的定义如下：

class TreeNode {
        
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
        
            this.val = val;
        }
    
    }

## 2. 二叉树遍历的实现 ##

二叉树有三种遍历方式，分为 先序遍历（根->左->右），中序遍历（左->根->右），后序遍历（左->右->根）。

#### 2.1 先序遍历 ####

##### 2.1.1 非递归实现 #####

借助栈结构，首先将 root 压入,出栈时访问其左右节点 , 然后先将 右子节点 压入，再将左子节点压入

// 前序遍历二叉树,广度优先 栈结构实现,将 root 压入,出栈,然后将 右子节点 左子节点压入
        public ArrayList<Integer> preOrder(TreeNode root) {
        
            if (root == null) return null;
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            ArrayList<Integer> result = new ArrayList<>();
            while (!stack.isEmpty()) {
        
                TreeNode current = stack.pop();
                result.add(current.val);
    
                if (null != current.right) {
        
                    stack.push(current.right);
                }
                if (null != current.left) {
        
                    stack.push(current.left);
                }
            }
            return result;
        }

##### 2.1.2 递归实现 #####

public void preOrder(TreeNode root, int orderMode) {
        
            if (root == null) {
        
                return;
            }
            System.out.print(root.val+",");
            preOrder(root.left, orderMode);
            preOrder(root.right, orderMode);
        }

#### 2.2 中序遍历 ####

##### 2.2.1 非递归实现 #####

借助栈结构，先将左节点压入栈,当节点为 null,栈顶元素出栈，获取val,将出栈元素的右节点压入栈

// 中序遍历二叉树,先将左节点压入栈,当节点为 null,栈顶元素出栈，获取val,将出栈元素的右节点压入栈
        public ArrayList inOrder(TreeNode root) {
        
            if (root == null) return null;
            Stack<TreeNode> stack = new Stack<>();
            ArrayList<Integer> result = new ArrayList<>();
            while (null != root || !stack.isEmpty()) {
        
                if (null != root) {
        
                    stack.push(root);
                    root = root.left;
                } else {
        
                    root = stack.pop();
                    result.add(root.val);
                    root = root.right;
    
                }
            }
            return result;
        }

##### 2.2.2 递归实现 #####

public void inOrder(TreeNode root, int orderMode) {
        
            if (root == null) {
        
                return;
            }
            inOrder(root.left, orderMode);
            System.out.print(root.val+",");
            inOrder(root.right, orderMode);
        }

#### 2.3 后序遍历 ####

##### 2.3.1 非递归实现 #####

深度优先,两个栈实现。在current 栈中入栈为 root，随即弹出到 back 栈；current 弹出节点如有左右节点，则按照先左后右的顺序一并入栈，之后出栈到 back中，back存储的数据依次出栈即为后序遍历序列。

// 后序遍历二叉树(深度优先),两个栈实现
        public ArrayList<Integer> sufOrder(TreeNode root) {
        
            if (root == null) return null;
            Stack<TreeNode> current = new Stack<>();
            Stack<TreeNode> back = new Stack<>();
            current.push(root); // 压入当前栈
    
            while (!current.isEmpty()) {
        
                TreeNode node = current.pop();
                back.push(node);// 将 current 弹出的元素压入back 栈
    
                if (null != node.left) {
        
                    current.push(node.left);
                }
                if (null != node.right) {
        
                    current.push(node.right);
                }
            }
            ArrayList<Integer> result = new ArrayList<>();
            while (!back.isEmpty()) {
        
                TreeNode node = back.pop();
                result.add(node.val);
            }
            return result;
        }

##### 2.3.2 递归实现 #####

public void sufOrder(TreeNode root, int orderMode) {
        
            if (root == null) {
        
                return;
            }
            sufOrder(root.left, orderMode);
            sufOrder(root.right, orderMode);
            System.out.print(root.val+",");
        }