跳转至

树#
发布于2021-01-18
上次编辑2021-04-19

二叉树#

结构定义#

1
2
3
4
5
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

1
2
3
4
5
6
7
8
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

二叉树的遍历#

使用队列进行层序遍历。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def levelorder(root: TreeNode, res: List[List[int]]) -> None:
    if root is None: return

    q = deque([root])
    while q:
        n = len(q)
        res.append([])

        for _ in range(n):
            node = q.popleft()
            res[-1].append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    void levelorder(TreeNode *root, vector<vector<int>> &res) {
        if (!root) return ;

        queue<TreeNode*> q; q.emplace(root);
        while (!q.empty()) {
            int n = q.size();
            res.emplace_back();
            for (int i = 0; i < n; ++i) {
                auto node = q.front(); q.pop();
                res.back().emplace_back(node->val);
                if (node->left) q.emplace(node->left);
                if (node->right) q.emplace(node->right);
            }
        }
    }

先序遍历：父结点-->左孩子-->右孩子
中序遍历：左孩子-->父结点-->右孩子
后序遍历：左孩子-->右孩子-->父结点

递归的写法很简单。

1
2
3
4
5
def preorder(root: TreeNode, res: List[int]) -> None:
    if root is None: return
    res.append(root.val)
    preorder(root.left, res)
    preorder(root.right, res)

1
2
3
4
5
6
void preorder(TreeNode *root, vector<int> &res) {
    if (!root) return ;
    res.emplace_back(root->val);
    preorder(root->left, res);
    preorder(root->right, res);
}

1
2
3
4
5
def inorder(root: TreeNode, res: List[int]) -> None:
    if root is None: return
    inorder(root.left, res)
    res.append(root.val)
    inorder(root.right, res)

1
2
3
4
5
6
void inorder(TreeNode *root, vector<int> &res) {
    if (!root) return ;
    inorder(root->left, res);
    res.emplace_back(root->val);
    inorder(root->right, res);
}

1
2
3
4
5
def postorder(root: TreeNode, res: List[int]) -> None:
    if root is None: return
    postorder(root.left, res)
    postorder(root.right, res)
    res.append(root.val)

1
2
3
4
5
6
void postorder(TreeNode *root, vector<int> &res) {
    if (!root) return ;
    postorder(root->left, res);
    postorder(root->right, res);
    res.emplace_back(root->val);
}

非递归写法可以模拟递归写法的栈调用。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def preorder(root: TreeNode, res: List[int]) -> None:
    s = [[1, root]]
    while s:
        p = s[-1]
        if p[1] is None:
            s.pop()
            continue

        if p[0] == 1:
            p[0] = 2
            res.append(p[1].val)
        elif p[0] == 2:
            p[0] = 3
            s.append([1, p[1].left])
        else:
            s.pop()
            s.append([1, p[1].right])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
void preorder(TreeNode *root, vector<int> &res) {
    stack<pair<int, TreeNode*>> s; s.emplace(make_pair(1, root));

    while (!s.empty()) {
        auto &p = s.top();
        if (!p.second) { 
            s.pop(); 
            continue; 
        }

        if (p.first == 1) { 
            p.first = 2; 
            res.emplace_back(p.second->val); 
        } else if (p.first == 2) {
            p.first = 3;
            s.emplace(make_pair(1, p.second->left));
        } else {
            s.pop();
            s.emplace(make_pair(1, p.second->right));
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def inorder(root: TreeNode, res: List[int]) -> None:
    s = [[1, root]]
    while s:
        p = s[-1]
        if p[1] is None:
            s.pop()
            continue

        if p[0] == 1:
            p[0] = 2
            s.append([1, p[1].left])
        elif p[0] == 2:
            p[0] = 3
            res.append(p[1].val)
        else:
            s.pop()
            s.append([1, p[1].right])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
void inorder(TreeNode *root, vector<int> &res) {
    stack<pair<int, TreeNode*>> s; s.emplace(make_pair(1, root));

    while(!s.empty()) {
        auto &p = s.top();
        if (!p.second) {
            s.pop();
            continue;
        }

        if (p.first == 1) {
            p.first = 2;
            s.emplace(make_pair(1, p.second->left));
        } else if (p.first == 2) {
            p.first = 3;
            res.emplace_back(p.second->val);
        } else {
            s.pop();
            s.emplace(make_pair(1, p.second->right));
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def postorder(root: TreeNode, res: List[int]) -> None:
    s = [[1, root]]
    while s:
        p = s[-1]
        if p[1] is None:
            s.pop()
            continue

        if p[0] == 1:
            p[0] = 2
            s.append([1, p[1].left])

        elif p[0] == 2:
            p[0] = 3
            s.append([1, p[1].right])
        else:
            s.pop()
            res.append(p[1].val)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
void postorder(TreeNode *root, vector<int> &res) {
    stack<pair<int, TreeNode*>> s; s.emplace(make_pair(1, root));
    while (!s.empty()) {
        auto &p = s.top();
        if (!p.second) {
            s.pop();
            continue;
        }

        if (p.first == 1) {
            p.first = 2;
            s.emplace(make_pair(1, p.second->left));
        } else if (p.first == 2) {
            p.first = 3;
            s.emplace(make_pair(1, p.second->right));
        } else {
            s.pop();
            res.emplace_back(p.second->val);
        }
    }
}

关于先序和后序，还有一种更简单的非递归写法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def preorder(root: TreeNode, res: List[int]) -> None:
    if root is None: return

    s = [root]
    while s:
        node = s[-1]
        res.append(node.val)
        s.pop()

        if node.right:
            s.append(node.right)
        if node.left:
            s.append(node.left)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void preorder(TreeNode *root, vector<int> &res) {
    if (!root) return ;

    stack<TreeNode*> s; s.emplace(root);
    while (!s.empty()) {
        auto node = s.top(); s.pop();
        res.emplace_back(node->val);
        if (node->right) s.emplace(node->right);
        if (node->left) s.emplace(node->left);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def postorder(root: TreeNode, res: List[int]) -> None:
    if root is None: return

    s = [root]
    while s:
        node = s[-1]
        res.append(node.val)
        s.pop()

        if node.left:
            s.append(node.left)
        if node.right:
            s.append(node.right)

    res[:] = res[::-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void postorder(TreeNode *root, vector<int> &res) {
    if (!root) return ;

    stack<TreeNode*> s; s.emplace(root);

    while (!s.empty()) {
        auto node = s.top(); s.pop();
        res.emplace_back(node->val);
        if (node->left) s.emplace(node->left);
        if (node->right) s.emplace(node->right);
    }
    reverse(res.begin(), res.end());
}

平衡二叉树#

在平衡二叉树中每个结点的左右两个子树的高度差的绝对值不超过 1。

平衡二叉树判断#

\(\mathcal{O}(n^2)\)

1
2
3
4
5
6
7
8
class Solution:
    def height(self, root: TreeNode) -> int:
        if root is None: return 0
        return 1 + max(self.height(root.left), self.height(root.right))

    def isBalanced(self, root: TreeNode) -> bool:
        if root is None: return True
        return abs(self.height(root.left) - self.height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int height(TreeNode *root) {
        if (!root) return 0;
        return 1 + max(height(root->left), height(root->right));
    }
    bool isBalanced(TreeNode* root) {
        if (!root) return true;
        return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
};

\(\mathcal{O}(n)\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def height(root: TreeNode) -> int:
            if root is None: return 0

            left = height(root.left)
            right = height(root.right)

            if left == -1 or right == -1 or abs(left - right) > 1: return -1
            return 1 + max(left, right)

        return height(root) != -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int height(TreeNode *root) {
        if (!root) return 0;
        auto left = height(root->left), right = height(root->right);
        if (left == -1 || right == -1 || abs(left - right) > 1) return -1;
        return 1 + max(left, right);
    }
    bool isBalanced(TreeNode* root) {
        return height(root) != -1;
    }
};

翻转二叉树#

1
2
3
4
5
6
7
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None: return root
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

1
2
3
4
5
6
7
8
9
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return root;
        swap(root->left, root->right);
        invertTree(root->left), invertTree(root->right);
        return root;
    }
};

1
2
3
4
5
6
7
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None: return root
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.left, root.right = right, left
        return root

1
2
3
4
5
6
7
8
9
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return root;
        auto left = invertTree(root->left), right = invertTree(root->right);
        root->left = right, root->right = left;
        return root;
    }
};
返回顶部

在手机上阅读