# Road Map

打怪路线：

二叉树构建
二叉树深度优先遍历：144 -> 145 -> 146
二叉树层遍历：102 -> 104
二叉树的直径（左右子树分别讨论）： 543 -> 124

# 二叉树生成工具

力扣给出的二叉树 case 是完全二叉树数组

需要先初始化为 TreeNode* 树形结构

# 图形化

# 二叉树的遍历

二叉树有深度优先和广度优先两种遍历方式

其中深度优先遍历（dfs）又分为前序、中序、后序三种遍历方式

可以用递归和非递归方式实现

深度优先搜索
- 前序遍历
- 中序遍历
- 后序遍历
宽度优先搜索

# DFS 题目

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

# DFS 模板

搜索模板

public class Solution {
    public void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // do something with root
        traverse(root.left);
        // do something with root
        traverse(root.right);
        // do something with root
    }
}

1
2
3
4
5
6
7
8
9
10
11
12

分治模板

public class Solution {
    public ResultType traversal(TreeNode root) {
        // null or leaf
        if (root == null) {
            // do something and return;
        }

        // Divide
        ResultType left = traversal(root.left);
        ResultType right = traversal(root.right);

        // Conquer
        ResultType result = Merge from left and right.
        return result;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 前序遍历

遍历顺序：根左右

递归

func dfs(root){
    visit(root)
    dfs(root.left)
    dfs(root.right)
}

1
2
3
4
5

代码实现

class Solution {
private:
    vector<int > ans;
public:
    vector<int> preorderTraversal(TreeNode* root) {
        dfs(root);
        return ans;
    }
    void dfs(TreeNode* root){
        if (!root) return ;
        ans.push_back(root->val);
        dfs(root->left);
        dfs(root->right);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

非递归方式

用指针 p 表示当前位置，用一个来栈记录访问顺序

对于每一个当前节点 p，先访问 p, 然后右子树入栈，然后访问左子树

栈S;
p= root;
while(p || S不空){
    while(p){
        访问p节点；
        p的右子树入S;
        p = p的左子树;
    }
    p = S栈顶弹出;
}

1
2
3
4
5
6
7
8
9
10

代码实现

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        TreeNode* p = root;
        vector<TreeNode*> stk;
        while (p || !stk.empty()){
            while (p){
                ans.push_back(p->val);
                stk.push_back(p->right);
                p = p->left;
            }
            p = stk.back();
            stk.pop_back();
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 中序遍历

中序遍历：左根右

递归方式

func dfs(root){
    dfs(root.left)
    visit(root)
    dfs(root.right)
}

1
2
3
4
5

非递归方式

思路：

先把左子树都进栈，依次出栈，访问左子树，出栈过程把右子树都入栈，这样访问的顺序就是左根右；用一个指针 p 标记当前游标，一个栈保存访问顺序

对于每一个当前节点 p，先把左节点全部入栈，在出栈的过程中，依次访问根节点，右子树

栈S;
p = root;
while(p || S不空){
    while(p){
        p入S;
        p = p的左子树;
    }
    p = S.top 出栈;
    访问p;
    p = p的右子树;
}

1
2
3
4
5
6
7
8
9
10
11

cpp 代码实现

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<TreeNode*> stk = {};
        vector<int> ans;
        TreeNode* p = root;
        while (p || !stk.empty()){
            while(p){
                stk.push_back(p);
                p = p->left;
            }
            p = stk.back();
            ans.push_back(p->val);
            stk.pop_back();
            p = p->right;
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 后序遍历

# 递归思路

var postorderTraversal = function (root) {
  let ans = [];
  function dfs(root) {
    if (!root) return;
    dfs(root.left);
    dfs(root.right);
    ans.push(root.val);
  }
  dfs(root);
  return ans;
};

1
2
3
4
5
6
7
8
9
10
11

# 非递归思路

先得到根右左，然后逆序得到左右根

得到根右左的过程类似先序得到根左右，先把右子树访问完，把左子树压栈

栈S;
p= root;
while(p || S不空){
    while(p){
        访问p节点；
        p的左子树入S;
        p = p的右子树;
    }
    p = S栈顶弹出;
}
结果序列逆序;

1
2
3
4
5
6
7
8
9
10
11

代码实现：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        vector<TreeNode*> stk;
        TreeNode* p = root;
        while (p || !stk.empty()){
            while(p){
                ans.push_back(p->val);
                stk.push_back(p->left);
                p = p->right;
            }
            p = stk.back();
            stk.pop_back();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

← 0x16_Trie 0x18_优先队列 →