LeetCode【5】二叉树的遍历（N叉树的遍历）

1.先序遍历：按照根节点->左子树->右子树的顺序访问二叉树

先序遍历：（1）访问根节点；（2）采用先序递归遍历左子树；（3）采用先序递归遍历右子树；

Leetcode144题就是这个问题

题目链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/description/

题目描述：

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

 示例:

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

输出: [1,2,3]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

先给出递归的实现方法

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

    }

 

2.中序遍历：按照左子树->根节点->右子树的顺序访问

中序遍历：（1）采用中序遍历左子树；（2）访问根节点；（3）采用中序遍历右子树

Leetcode的94题就是这个题目

题目链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/description/

题目描述：

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

示例:

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

输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

这里先给出递归解法

public class BinaryTreeInorderTraversal_94 {
    List<Integer> result = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null){
            return  result;
        }else {
            inorderTraversal(root.left);
            result.add(root.val);
            inorderTraversal(root.right);
            return result;
        }
    }

}

 

3.后序遍历

后序遍历：（1）采用后序递归遍历左子树；（2）采用后序递归遍历右子树；（3）访问根节点；

Leetcode的145就是二叉树的后序遍历问题

题目链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/description/

题目描述：

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

示例:

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

输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

这里先给出递归解法。

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