樹的概念與名詞解釋

樹（Tree）是一種抽象的數(shù)據(jù)結(jié)構(gòu)丛楚，之所以把“它”叫做樹族壳，是因為它看起來像是一棵倒掛著的樹，即根在上趣些，葉朝下仿荆。

一棵樹是由n（n>=0）個元素組成的，當(dāng)n = 0時坏平，樹稱為空(null或empty)樹拢操。每個元素稱為一個節(jié)點(node)，而最頂端的節(jié)點成為根節(jié)點舶替。

樹中的名詞和概念很多令境，在這里需要有個大概的了解：

二叉樹

看到上面樹的度孵延，引出了我們算法中常見的一類樹結(jié)構(gòu) 二叉樹吕漂。所謂二叉樹，就是每個節(jié)點最多含有兩個子樹（左子樹和右子樹）的樹稱為二叉樹尘应。

而針對二叉樹的結(jié)構(gòu)與數(shù)據(jù)存儲又分為了以下幾種類型：

二叉樹的定義

一般而言坯屿，二叉樹的算法題目都是以鏈?zhǔn)酱鎯Φ姆蔷€性結(jié)構(gòu)油湖。力扣上涉及二叉樹的題目，都會默認定義好樹的結(jié)構(gòu)领跛，定義方式如下：

Python：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

Java:

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

二叉樹的三種基礎(chǔ)遍歷

二叉樹的題目乏德，絕大多數(shù)都是在考樹的搜索。其中入門的是二叉樹的前吠昭、中喊括、后序遍歷：

• 前序遍歷：遍歷順序規(guī)則為【根左右】
• 中序遍歷：遍歷順序規(guī)則為【左根右】
• 后序遍歷：遍歷順序規(guī)則為【左右根】

舉個例子：

• 逐層遍歷：EAGCFBD
• 前序遍歷：EACBDGF
• 中序遍歷：ABCDEGF
• 后序遍歷：BDCAFGE

逐層遍歷，其實就是上節(jié)課講解隊列的基礎(chǔ)操作時矢棚，涉及到的二叉樹的廣度優(yōu)先搜索郑什。剩下的三種遍歷方式，大家可以對照下是否和你想的結(jié)果一樣蒲肋。

那么蘑拯，我們該通過什么方式來實現(xiàn)二叉樹的遍歷操作呢？有遞歸 肉津、 迭代兩種方式强胰。

遞歸比較好理解，迭代又是什么妹沙？其實，遞歸的操作熟吏，是隱式的通過棧內(nèi)存完成遞歸距糖。而迭代則需要我們自己模擬棧內(nèi)存。讓我們拿一道題目來練練手吧牵寺。

144.二叉樹的前序遍歷

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

難度：簡單

題目

給你二叉樹的根節(jié)點 root 悍引，返回它節(jié)點值的 前序 遍歷。
提示：

• 樹中節(jié)點數(shù)目在范圍 [0, 100] 內(nèi)
• -100 <= Node.val <= 100

進階：遞歸算法很簡單帽氓，你可以通過迭代算法完成嗎趣斤？

示例

示例 1：
    1
     \
      2
    / 
   3  
輸入：root = [1,null,2,3]
輸出：[1,2,3]

分析

先來說說遞歸，使用遞歸的方式來完成前中后遍歷黎休，只需要修改遞歸函數(shù)的節(jié)點順序即可完成浓领。
牢記如下訪問順序即可玉凯。

• 前序遍歷：遍歷順序規(guī)則為【根左右】
• 中序遍歷：遍歷順序規(guī)則為【左根右】
• 后序遍歷：遍歷順序規(guī)則為【左右根】

至于迭代，這需要我們將遞歸過程中隱式的內(nèi)存棧联贩，通過自己定義的方式來實現(xiàn)漫仆。
這里則要求我們，在掌握之前學(xué)習(xí)的鏈表和棧的操作基礎(chǔ)上泪幌，才更好理解這道題目盲厌。

1. 首先，我們需要創(chuàng)建一個棧祸泪，然后創(chuàng)建cur節(jié)點指向root
2. 然后當(dāng)椔鸷疲或者cur節(jié)點不為空時，啟動while循環(huán)操作
3. 由于第一個入棧的是root節(jié)點没隘，則我們直接保存它的值
4. 然后循環(huán)獲取當(dāng)前指針的左子樹指針（即cur.left）拓萌，保存值并加入棧中，直到指向葉子結(jié)點終止
5. 之后彈出當(dāng)前棧升略，將指針指向cur.right繼續(xù)上述操作微王。
6. 直到最終遍歷完成，返回節(jié)點的所有值品嚣。

讓我們來看看代碼的具體實現(xiàn)

遞歸解題

Python：

class Solution:
    def preorderTraversal(self, root):
        ret = []
        def dfs(tree):
            if not tree:
                return 
            if tree:
                ret.append(tree.val)
                dfs(tree.left)
                dfs(tree.right)
        dfs(root)
        return ret

Java：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        dfs(root, ret);
        return ret;
    }

    private void dfs(TreeNode tree, List<Integer> ret){
        if (tree == null){
            return;
        }
        ret.add(tree.val);
        dfs(tree.left, ret);
        dfs(tree.right, ret);
    }
}

迭代解題

Python：

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        ret = list()
        if not root:
            return ret

        stack = []
        cur = root
        while stack or cur:
            while cur:
                ret.append(cur.val)
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            cur = cur.right
        return ret

Java：

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

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                ret.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            cur = cur.right;
        }
        return ret;
    }
}

通過這道題炕倘，讓大家對二叉樹的遍歷有所了解，下來大家可以完成這兩道題目翰撑，用以加深了解罩旋。

• 94. 二叉樹的中序遍歷

• 145. 二叉樹的后序遍歷

今天的樹專題概念篇就到這里，明天就要正式開始刷題之旅了眶诈，基礎(chǔ)很重要一定要吃透了在往后走哦涨醋，明天見！

歡迎關(guān)注我的公眾號: 清風(fēng)Python逝撬，帶你每日學(xué)習(xí)Python算法刷題的同時浴骂，了解更多python小知識。

我的個人博客：https://qingfengpython.cn

力扣解題合集：https://github.com/BreezePython/AlgorithmMarkdown