【数据结构】二叉树：LeetCode题（一）94. 二叉树的中序遍历，144. 二叉树的前序遍历，145. 二叉树的后序遍历，102. 二叉树的层序遍历

妖狐艹你老母 2022-12-12 08:24 142阅读 0赞

文章开始前，先放个传送门 [二叉树特性浅析及Java实现DFS、BFS][Java_DFS_BFS]。那么，这篇我们就来看看二叉树在LeetCode最基本的三个题：中序遍历，前序遍历，后序遍历，层序遍历。其实解法真没什么说的了，都是八股文…

## [94. 二叉树的中序遍历²][94.] ##

给定一个二叉树，返回它的*中序* 遍历。

**示例:**

输入: [1,null,2,3]
       1
        \
         2
        /
       3
    
    输出: [1,3,2]

### 解法一：递归 ###

中序：左根右，将根换成add()就行

class Solution {
        
        public List<Integer> inorderTraversal(TreeNode root) {
        
            List<Integer> res = new ArrayList<>();
            inOrder(root,res);
            return res;
        }
    
        private void inOrder(TreeNode node,List res) {
        
            if (node == null) return;
            inOrder(node.left,res);
            res.add(node.val);
            inOrder(node.right,res);
        }
    }

### 解法二：迭代 ###

递归是内部维护了一个函数调用栈，而使用迭代的话，就要自己用一个栈来保存所有结点，依次出栈并取值

public List<Integer> inorderTraversal(TreeNode root) {
        
            List<Integer> res = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
    		
            // root=null，树的非空判断
            // stack.isEmpty，树遍历完的判断
            while (root != null || !stack.isEmpty()) {
        
                // 遍历当前节点的所有左子树
                while (root != null) {
        
                    stack.push(root);
                    root = root.left;
                }
    	        // 栈顶此时是最左节点，出栈，取值
                root = stack.pop();
                res.add(root.val);
                
                // 处理下一个节点（子树）
                // 1.叶子节点了:root=root.right==null，但stack不是Empty，所以出栈当前节点的父节点
         		// 2.未到叶子节点，root=root.right，遍历当前节点的右子节点
                root = root.right;
            }
            return res;
        }

## [144. 二叉树的前序遍历²][144.] ##

给定一个二叉树，返回它的 *前序* 遍历。

**示例:**

输入: [1,null,2,3]  
       1
        \
         2
        /
       3 
    
    输出: [1,2,3]

### 解法一：递归 ###

前序：根左右，将根换成add()就行

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

### 解法二：迭代 ###

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

## [145. 二叉树的后序遍历³][145.] ##

给定一个二叉树，返回它的 *后序* 遍历。

**示例:**

输入: [1,null,2,3]  
       1
        \
         2
        /
       3 
    
    输出: [3,2,1]

### 解法一：递归 ###

后序：左右根，将根换成add()就行

class Solution {
        
        public List<Integer> postorderTraversal(TreeNode root) {
        
            List<Integer> res = new ArrayList<>();
            postOrder(root,res);
            return res;
        }
    
        public void postOrder(TreeNode root, List<Integer> res) {
        
            if (root == null) return;
            postOrder(root.left,res);
            postOrder(root.right,res);
            res.add(root.val);
        }
    }

### 解法二：迭代\* ###

public List<Integer> postorderTraversal(TreeNode root) {
        
    
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
    		
        stack.push(root);
        while(!stack.empty()){
        
            root = stack.pop();
            res.add(0, root.val); // 头插
            if(root.left != null) stack.push(root.left); // 与前序遍历相反
            if(root.right != null) stack.push(root.right);
        }
        return res;
    }

## [102. 二叉树的层序遍历²][102.] ##

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：  
二叉树：\[3,9,20,null,null,15,7\],

3
       / \
      9  20
        /  \
       15   7

返回其层次遍历结果：

[
      [3],
      [9,20],
      [15,7]
    ]

### 解法：BFS ###

public List<List<Integer>> levelOrder(TreeNode root) {
        
            if (root == null) return new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            List<List<Integer>> res = new ArrayList<>();
    
            while (!queue.isEmpty()) {
        
                List<Integer> list = new ArrayList<>();
                int size = queue.size();
                for (int i = 0; i < size; i++) {
        
                    TreeNode node = queue.poll();
                    list.add(node.val);
                    if (node.left != null) queue.offer(node.left);
                    if (node.right != null) queue.offer(node.right);
                }
                res.add(list);
            }
            return res;
        }

[Java_DFS_BFS]: https://blog.csdn.net/weixin_43935927/article/details/108932834
[94.]: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
[144.]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
[145.]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
[102.]: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/