代码随想录-43-144. 二叉树的前序遍历、44-94. 二叉树的中序遍历、45-145. 二叉树的后序遍历

前言

在本科毕设结束后，我开始刷卡哥的“代码随想录”，每天一节。自己的总结笔记均会放在“算法刷题-代码随想录”该专栏下。
代码随想录此题链接

题目

略

1.递归的思想

思路（定义变量）

• TreeNode 树节点的类
• 封装结果的List

通解思路

三步

1. 确定输入输出值
2. 确定递归的退出条件
3. 确定递归一般性处理方法

2. 本题思路分析：

1. 输入为树（TreeNode类）和封装输出结果的数据结构
2. 当遍历到当前节点（类）为空时退出递归
3. 通过观察其是前、中、后序，来决定执行顺序。
   前：
   先中间节点（存入节点值），再左孩子节点（递归左孩子），最后右孩子节点（递归右孩子）
   中：
   先左孩子节点（递归左孩子），再中间节点（存入节点值），最后右孩子节点（递归右孩子）
   后：
   先左孩子节点（递归左孩子），再右孩子节点（递归右孩子），最后中间节点（存入节点值）

3. 算法实现

• 代码：
  统一的树节点类

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;
     }
}
1
2
3
4
5
6
7
8
9
10
11
12

前序

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<Integer>();
    travelTreeNode(root,result);
    return result;
}

public void travelTreeNode(TreeNode curNode,List<Integer> result){
        if(curNode == null){
            return;
        }else{
            result.add(curNode.val);
            travelTreeNode(curNode.left,result);
            travelTreeNode(curNode.right,result);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

中序

public List<Integer> inorderTraversal(TreeNode root) {
   List<Integer> result = new ArrayList<Integer>();
    travelTreeNode(root,result);
    return result;
}

public void travelTreeNode(TreeNode curNode,List<Integer> result){
    if(curNode == null){
        return;
    }else{
        travelTreeNode(curNode.left,result);
        result.add(curNode.val);
        travelTreeNode(curNode.right,result);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

后序

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<Integer>();
    travelTreeNode(root,result);
    return result;
}

public void travelTreeNode(TreeNode curNode,List<Integer> result){
    if(curNode == null){
        return;
    }else{
        travelTreeNode(curNode.left,result);
        travelTreeNode(curNode.right,result);
        result.add(curNode.val);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4. pop函数的算法复杂度

略

5. 算法坑点

略