Leetcode - 二叉树遍历系列

爱被打了一巴掌 2022-09-10 00:20 35阅读 0赞

### Leetcode - 二叉树遍历系列 ###

*   *   *  1. 前序遍历
         *   *   *  1.1 递归写法
                 *  1.2 非递归写法
         *  2. 中序遍历
         *   *   *  2.1 递归写法
                 *  2.2 非递归写法
         *  3. 后序遍历
         *   *   *  3.1 递归写法
                 *  3.2 非递归写法
         *  4. 层次遍历
         *   *   *  4.1 非递归写法

Leetcode链接：

*  [144. 二叉树的前序遍历][144.]
 *  [94. 二叉树的中序遍历][94.]
 *  [145. 二叉树的后序遍历][145.]

### 1. 前序遍历 ###

题目：[144. 二叉树的前序遍历][144.]

##### 1.1 递归写法 #####

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        List<Integer> res = new ArrayList<Integer>();
        public List<Integer> preorderTraversal(TreeNode root) {
        
            //二叉树的深度遍历
            dfs(root);
            return res;
        }
    
        public void dfs(TreeNode root){
        
            if(root == null) return;
            res.add(root.val);
            dfs(root.left);
            dfs(root.right);
        }   
    }

##### 1.2 非递归写法 #####

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        
        public List<Integer> preorderTraversal(TreeNode root) {
        
            List<Integer> res = new ArrayList<Integer>();
            if(root == null) return res;
    
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
    
            while(!stack.isEmpty()){
        
                TreeNode temp = stack.pop();
                res.add(temp.val);
    
                if(temp.right != null) stack.push(temp.right);
                if(temp.left != null) stack.push(temp.left);
            }
    
            return res;
        } 
    }

### 2. 中序遍历 ###

题目：[94. 二叉树的中序遍历][94.]

##### 2.1 递归写法 #####

##### 2.2 非递归写法 #####

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public List<Integer> inorderTraversal(TreeNode root) {
        
            List<Integer> res = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode curr = root;
            while(curr != null || !stack.isEmpty()){
        
                if(curr != null){
        
                    stack.add(curr);
                    curr = curr.left;
                }else{
        
                    curr = stack.pop();
                    res.add(curr.val);
                    curr = curr.right;
                }
            }
            return res;
        }
    }

### 3. 后序遍历 ###

题目：[145. 二叉树的后序遍历][145.]

##### 3.1 递归写法 #####

##### 3.2 非递归写法 #####

我们分析下前序遍历非递归写法，顺序是`root->left->right`，现在需要`left->right->root`

**思路**：考虑把前序的left和right对调位置，变成`root->right->left`，然后反转变成`left->right->root`

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public List<Integer> postorderTraversal(TreeNode root) {
        
            List<Integer> res = new ArrayList<>();
            if(root == null) return res;
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while(!stack.isEmpty()){
        
                TreeNode temp = stack.pop();
                res.add(temp.val);
                if(temp.left != null) stack.push(temp.left);
                if(temp.right != null) stack.push(temp.right);
            }
            Collections.reverse(res);
            return res;
        }
    }

### 4. 层次遍历 ###

BFS应用场景的大佬总结：[https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/][https_leetcode-cn.com_problems_binary-tree-level-order-traversal_solution_bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l]

##### 4.1 非递归写法 #####

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public List<List<Integer>> levelOrder(TreeNode root) {
        
            List<List<Integer>> res = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            if(root == null) return res;
            queue.offer(root);
            while(!queue.isEmpty()){
        
                int size = queue.size();
                List<Integer> item = new ArrayList<>();
                for(int i = 0; i < size; i++){
        
                    TreeNode node = queue.poll();
                    item.add(node.val);
    
                    if(node.left != null) queue.offer(node.left);
                    if(node.right != null) queue.offer(node.right);
                }
                res.add(item);
            }
            return res;
        }
    }

[144.]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
[94.]: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
[145.]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
[https_leetcode-cn.com_problems_binary-tree-level-order-traversal_solution_bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l]: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/