二叉树的前中后序遍历

思路

首先,需要明白分解递归的四个步骤:

  • 第一步:从小到大递推
  • 第二步:分情况讨论,明确结束条件
  • 第三步:组合出完整方法
  • 第四步:想验证,则从大到小画图推演

1.从小到大递推

假设有这样一颗树

    3
   / \
  9  20
    /  \
   15   7

这时候是从外到内访问的,当访问一个最小子树20的时候

void visit1(){
    list.add(root);//20被访问
    root.left;//继续访问15
    root.right; //继续访问7
    }

向上追溯

void visit2(){
    list.add(root);//3被访问
    root.left;//继续访问,得到9
    root.right; //继续访问,得到20
  }

这时候我们将他们合并在一起,于是有了递归;此处也可以是递归的代码实现

void visit(){
    list.add(root);//20被访问
    visit(root.left);//继续访问15
    visit(root.right); //继续访问7
 }

2.结束条件

一般情况下,当root为null时,结束

3.组合出完整方法

完整的代码实现

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 static void inOrderRecur(TreeNode head) {
    if (head == null) {
        return;
    }
    inOrderRecur(head.left);//中间节点先向下
    System.out.print(head.value + " ");//自身
    inOrderRecur(head.right);//右节点
}

后序同理

public static void postOrderRecur(TreeNode head) {
    if (head == null) {
        return;
    }
    postOrderRecur(head.left);//前
    postOrderRecur(head.right);//后
    System.out.print(head.value + " ");//最后是中间节点
}

4.从大到小 画图推演

image-20231221215212067

来道题练个手

递归实现三种遍历

L144 二叉树前序遍历问题

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList();
        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);

    }
}

L94 递归中序遍历

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

    }
}

L145 递归后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList();
        preOrder(root, res);
        return res;
    }

    public void preOrder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }

        preOrder(root.left, res);

        preOrder(root.right, res);
        res.add(root.val);
    }
}

递归的不同唯一区别就是什么时候处理结果,如果想不明白可以想什么时候最底层的节点为null时的场景;

可以试试迭代实现树的遍历,下面是练习

迭代题目实现

1.前序遍历

如果还有左子树就一直向下找。完了之后再返回从最底层逐步向上向右找。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
       //这里的顺序没有要求,两边可以切换
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                // 走到左子树最底层为null时候
                res.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            //node这里表示的是某一个子树,当一个字数便利完后会通过栈到另一个子树
            node = node.right;

        }
        return res;
    }
}

2.中序遍历

中序遍历是左中右,先访问的是二叉树左子树的节点,然后一层一层向下访问, 直到到达树左面的最底部,再开始处理节点(也就是在把节点的数值放进res列表中

这里使用的临时变量node可以省略,直接使用root节点也可以

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
  List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node =root;  
        while (node!=null||!stack.isEmpty()){
            while (node !=null){
                stack.push(node);
                node = node.left;
            }
            //执行到此处到达最底层,然后借助栈实现遍历
            node = stack.pop();
            res.add(node.val);
            node = node.right;
        }
        return res;
    }
}

3.后序遍历

这里说明的是反转法,常用的三种除了反转法还有: 访问标记法、和Morris法

能发现的是,后序遍历和前序遍历只是顺序不同,只需要将前序的左右交换并将结果反转就可以得到后序遍历了

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
 List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                res.add(node.val);
                stack.push(node);
                node = node.right;// 左右交换
            }
            node = stack.pop();
            node = node.left; //左右交换    

        }
        Collections.reverse(res); //使用集合反转
        return res;
    }
      }