树（入门篇）

树是一种数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。本篇主要就树的一些基础部分进行一些梳理，所有代码均在LeetCode或PAT上Accepted

二叉树相关概念

树的相关概念

在数据结构中把树枝分叉处、树叶、树根抽象为节点（node），其中树根抽象为根节点，且对于一棵树来说最多存在一个根节点；把树叶概括为叶子节点，且叶子节点不再延伸出新的节点；把茎干和树枝统一抽象为边。这样，树就被定位为若干个节点和若干条边组成的数据结构，且在树中的结点不能被边连接成环。

• 树可以没有结点，这种情况下被称为空树
• 树的层次(layer)从根节点开始计算，即根节点为第一层，根节点子树的根节点为第二层
• 把结点的子树棵树称为结点的度(degree)，而树中结点最大的度称为树的度。（二叉树的树度为2）
• 由于一条边连接两个结点，且树中不存在环，因此对有n个结点的树，边数一定是n-1。且满足连通、边数等于顶点数 - 1的结构一定是树。
• 叶子节点被定义为度为0的结点，因此当树中只有一个结点（根节点）时，根节点也算叶子结点
• 结点的深度(depth)是指从根节点（深度为1）开始自顶向下逐层累加至该节点时的深度值；结点的高度（height）是指从最底层叶子结点（高度为1）开始自底向上逐层累加至该节点时的高度。树的高度是指树中结点的最大高度。对树而言，深度和高度是相等的，对结点而言不一定。
• 多棵树组合在一起称为森林（forest）

二叉树及特殊的二叉树

二叉树递归定义：

1、要么二叉树没有根节点，是一棵空树

2、要么二叉树由根节点、左子树、右子树组成，且左子树和右子树都是二叉树

• 二叉树和度为2的树区别：度为2的树只能说明树中每个结点的子节点个数不超过2。二叉树虽然满足，但是二叉树严格区分左右子树，不能随意交换左子树和右子树的位置。
• 满二叉树：每一层的结点个数都达到了该层所能达到的最大结点个数
• 完全二叉树：除了最下面一层外，其余层的结点个数都达到了当层所能达到的最大结点树

二叉树的主要性质

• 在二叉树中，第i层上最多有2i个结点（ i≥0 ）
• 深度为k的二叉树至多有2^k+1 - 1个结点（ k≥0 ）其中深度(depth)定义为二叉树中层数最大的叶结点的层数
• 一棵二叉树，若其终端结点数为n₀，度为2的结点数为n₂ ，则n₀ = n₂ + 1
• 满二叉树定理：非空满二叉树树叶数目等于其分支结点数加1
• 满二叉树定理推论：一个非空3叉树的空子树数目等 于其结点数加1
• 有n个结点（ n > 0 ）的完全二叉树的高度为 ⌈log₂ (n+1)⌉（深度为⌈log₂ (n+1)⌉ - 1 ）

二叉树的存储结构

LinkedList是特殊化的Tree；Tree是特殊化的Graph

二叉树顺序存储结构

完全二叉树：从上至下、从左到右存储n个结点的完全二叉树的结点父子关系：

• 非根节点（序号i > 1）的父节点序号是**⌊i/2⌋**
• 结点（序号为i）的左孩子结点序号是2i，（若2i <= n，否则没有左孩子）
• 结点（序号为i）的左孩子结点序号是2i + 1，（若2i <= n，否则没有左孩子）

一般二叉树可以采用这种结构，但会造成空间浪费

二叉树链表存储

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x):val(x),left(NULL),right(NULL){}
}

public class TreeNode {
    public int val;
    public TreeNode left,right;
    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

二叉树的遍历

我们统一结点类型为

struct TreeNode {
    int val;			// 数据域
    TreeNode* left;		// 指向左子树根节点指针
    TreeNode* right;	// 指向右子树根节点指针
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

先中后递归遍历

先序

​ 访问根节点

​ 先序遍历其左子树

​ 先序遍历其右子树

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

中序

​ 中序遍历左子树

​ 访问根节点

​ 中序遍历右子树

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if (root != NULL) {
            inorderTraversal(root->left);
            res.push_back(root->val);
            inorderTraversal(root->right);
        }
    }
private:
    vector<int> res;
}; 

后序

​ 后序遍历左子树

​ 后序遍历右子树

​ 访问根节点

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(root != NULL) {
            postorderTraversal(root->left);
            postorderTraversal(root->right);
            res.push_back(root->val);
        }
        return res;
    }
private:
    vector<int> res;
}; 

先中后非递归遍历

先序、中序和后序遍历过程：遍历过程中经过结点的路线是一样的，只是访问各结点的时机不同

先序遍历和中序遍历的，区别在于第一次访问结点和第二次访问结点什么时候打印结点的问题

T = root;
while(栈不空 || T != NULL) {
	while(T != NULL) {
		第一次访问结点;T进栈		// printf ==> 先序
		T = T->lchild;
	}
	// 以下考虑栈顶结点
	while(栈不空) {
		第二次访问结点;出栈;		// printf ==> 中序
		T = T->rchild;
	}
}

先序

第一次碰到结点就打印（压栈操作的时候）

• 遇到一个结点就把它压栈打印，并去遍历它的左子树
• 当左子树遍历结束后，从栈顶弹出这个结点
• 然后按照其右指针在去先序遍历该结点的右子树

class Solution {
public:
    /**
     * @brief 先序遍历非递归算法
     * @param root 
     * @return vector<int> 
     */
    vector<int> preorderTraversal(TreeNode* root) {
        TreeNode* T = root;
        vector<int> res;
        stack <TreeNode*> s;
        while (T != NULL || !s.empty()) {
            // 遇到第一个结点就压栈，并去遍历左子树
            while (T != NULL) {
                // 第一次访问结点就加到结果集
                res.push_back(T->val);
                s.push(T);
                T = T->left;
            }
            if (!s.empty()) {
                // 左子树遍历结束，弹出栈顶元素
                T = s.top();
                s.pop();
                T = T->right;
            }
        }
        return res;
    }
};

中序

第二次碰到结点就打印（出栈操作的时候）

• 遇到一个结点就把它压栈，并去遍历它的左子树
• 当左子树遍历结束后，从栈顶弹出这个结点并访问它
• 然后按照其右指针在去中序遍历该结点的右子树

class Solution {
public:
    /**
     * @brief 中序遍历非递归算法
     * @param root 
     * @return vector<int> 
     */
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* T = root;
        vector<int> res;
        stack<TreeNode*> s;
        while (T != NULL || !s.empty()) {
            // 遇到第一个结点就压栈，并遍历左子树
            while (T != NULL) {
                s.push(T);
                T = T->left;
            }
            if (!s.empty()) {
                // 左子树遍历结束，从栈顶弹出结点并访问
                T = s.top();
                s.pop();
                res.push_back(T->val);
                // 按右指针去中序遍历该结点右子树
                T = T->right;
            }
        }
        return res;
    }
};

后序

我们不妨来思考先序遍历的顺序是 根-左-右，我们很容易能够变成根-右-左，那么后序遍历恰好是这种结果的一个倒序，我们就可以采用栈来保存根-右-左这种遍历结果的顺序，然后依次出栈就是后序遍历结果

class Solution {
public:
    /**
     * @brief 后序遍历非递归算法 ==> 中序遍历稍作修改
     * @param root 
     * @return vector<int> 
     */
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode* T = root;
        while (T != NULL || !s.empty()) {
            // 遇到第一个结点就压栈，并去访问右子树，将结果放在前面
            while (T != NULL) {
                s.push(T);
                res.insert(res.begin(),T->val);
                T = T->right;
            }
            // 访问栈顶元素，遍历结点左子树
            if (!s.empty()) {
                T = s.top();
                s.pop();
                T = T->left;
            }
        }
        return res;
    }
};

层次遍历

层次遍历是按照层次的顺序从根节点向下逐层进行遍历，而且对每一层的结点从左到右进行

BFS思想 ==> 使用队列实现

class Solution {
public:
    /**
     * @brief 层序遍历：使用队列 BFS 思想
     * @param root 
     * @return vector<vector<int>> 
     */
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if (root == NULL) {
            return res;
        }
        q.push(root);
        while (!q.empty()) {
            vector<int> v;
            // 使用count记录每一层的个数
            int count = q.size();
            while (count--) {
                TreeNode* T;
                T = q.front();
                q.pop();
                v.push_back(T->val);
                if (T->left != NULL) {
                    q.push(T->left);
                }        
                if (T->right != NULL) {
                    q.push(T->right);
                }
            }
            res.push_back(v);
        }
        return res;
    }
};

二叉树遍历的应用

以下我们统一数据结点为：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

输出二叉树的叶子结点

在二叉树遍历算法中增加检测结点的“左右子树是否都为空”

void PreOrderPrintLeaves (TreeNode* root) {
  if (root != NULL) {
    if (root->left == NULL && root->right == NULL) {
      printf("%d\n", root->val);
    }
    PreOrderPrintLeaves(root->left);
    PreOrderPrintLeaves(root->right);
  }
}

求二叉树的高度

递归解法

int maxDepth(TreeNode* root) {
    if (root == NULL) {
      return 0;
    }
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

BFS解法

我们也可以使用层序遍历二叉树，然后计数总层数，即为二叉树的最大深度

class Solution {
public:
    /**
     * @brief 求树的最大深度
     * @param root 
     * @return int 
     */
    int maxDepth(TreeNode *root) {
        TreeNode *T = root;
        int res = 0;
        if (root == NULL) {
            return 0;
        }
        queue<TreeNode *> q;
        q.push(T);
        while (!q.empty()) {
            res++;
            // 一定要将 q.size() 放在初始化里，而不能放在判断停止的条件中
            // 因为q的大小是随时变化的，所以放停止条件中会出错
            for (int i = q.size(); i > 0; i--) {
                T = q.front();
                q.pop();
                if (T->left != NULL) {
                    q.push(T->left);
                }
                if (T->right != NULL) {
                    q.push(T->right);
                }
            }
        }
        return res;
    }
};

DFS解法

class Solution {
public:
    int max_depth = 0;
    int maxDepth(TreeNode* root) {
        if (root == NULL)
            return 0;
        dfs (root, 1);
        return max_depth;
    }
    /**
     * @brief DFS求最大深度
     * @param root 
     * @param depth 
     */
    void dfs (TreeNode* root, int depth) {
        // 是叶子结点，更新最大高度
        if (root->left == NULL && root->right == NULL) {
            max_depth = max(max_depth, depth); 
        }
        // 递归左子树
        if (root->left != NULL)
            dfs(root->left, depth + 1);
        // 递归右子树
        if (root->right != NULL)
            dfs(root->right, depth + 1);
    }
};

两种遍历序列确定一颗二叉树

必须要知道中序序列才能去确定一颗二叉树

先序+中序

先序和中序遍历序列来确定一颗二叉树

• 根据先序序列第一个结点确定根节点
• 根据根节点在中序遍历序列中分割出左右两个子序列
• 对左子树和右子树分别递归使用相同的方法继续分解

• 如果递归过程中先序序列区间为[ps, pe]，中序序列为[is, ie]，pos为根节点在中序序列中的位置
• 左子树的结点个数为numLeft = pos - is，左子树的先序序列区间就是[ps + 1, ps + numLeft]，左子树的中序序列区间就是[is, pos - 1]
• 右子树的先序序列[ps + numLeft + 1, pe]，右子树的中序序列为[pos + 1, ie]

#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return create(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }

    TreeNode* create(vector<int>& preorder, vector<int>& inorder, int ps, int pe, int is, int ie){
        if(ps > pe){
            return nullptr;
        }
        TreeNode* node = new TreeNode(preorder[ps]);
        // 找中序序列的位置
        int pos;
        for(int i = is; i <= ie; i++){
            if(inorder[i] == node->val) {
                pos = i;
                break;
            }
        }
        int numLeft = pos - is;
        // 递归
        node->left = create(preorder, inorder, ps + 1, ps + numLeft, is, pos - 1);
        node->right = create(preorder, inorder, ps + numLeft + 1, pe, pos + 1, ie);
        return node;                            
    }
};

后序+中序

思路同前序序列和中序序列构造二叉树

• 如果递归过程中后序序列区间为[ps, pe]，中序序列为[is, ie]，pos为根节点在中序序列中的位置
• 左子树的结点个数为numLeft = pos - is，左子树的后序序列区间就是[ps, ps + numLeft - 1]，左子树的中序序列区间就是[is, pos - 1]
• 右子树的后序序列[ps + numLeft, pe - 1]，右子树的中序序列为[pos + 1, ie]

#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return create(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
    }
    TreeNode* create(vector<int>& inorder, vector<int>& postorder, int is, int ie, int ps, int pe) {
        if (ps > pe) {
            return nullptr;
        }
        TreeNode* node = new TreeNode(postorder[pe]);
        int pos;
        for (int i = is; i <= ie; i++) {
            if (inorder[i] == node->val) {
                pos = i;
                break;
            }
        }
        int numLeft = pos - is;
        node->left = create(inorder, postorder, is, pos - 1, ps, ps + numLeft - 1);
        node->right = create(inorder, postorder, pos + 1, ie, ps + numLeft, pe - 1);
        return node;
    }
};