二叉樹問題（一）-LeetCode 110、617、101、814、655、98、654（遞歸思路）
- 2019 年 12 月 24 日
- 筆記
作者：TeddyZhang，公眾號：演算法工程師之路
二叉樹問題（一）：
LeetCode # 110 617 101 814 655 98 654
1
編程題
【LeetCode #110】平衡二叉樹
給定一個二叉樹，判斷它是否是高度平衡的二叉樹。 本題中，一棵高度平衡二叉樹定義為： 一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過1
解題思路：自上而下遞歸得到每個子樹的高度，依據定義即可。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int height(TreeNode* node) { if (node == nullptr) return ; return max(height(node->left), height(node->right)) + ; } bool isBalanced(TreeNode* root) { if (root == nullptr) return true; int left = height(root->left); int right = height(root->right); return abs(left-right) <= && isBalanced(root->left) && isBalanced(root->right); } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/balanced-binary-tree/
【LeetCode #617】合併二叉樹
給定兩個二叉樹，想像當你將它們中的一個覆蓋到另一個上時，兩個二叉樹的一些節點便會重疊。 你需要將他們合併為一個新的二叉樹。合併的規則是如果兩個節點重疊，那麼將他們的值相加作為節點合併後的新值，否則不為 NULL 的節點將直接作為新二叉樹的節點。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { if (t1 == nullptr) return t2; if (t2 == nullptr) return t1; if (t1 && t2) { t1->val += t2->val; t1->left = mergeTrees(t1->left, t2->left); t1->right = mergeTrees(t1->right, t2->right); return t1; }else return nullptr; } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/merge-two-binary-trees
【LeetCode #101】對稱二叉樹
給定一個二叉樹，檢查它是否是鏡像對稱的。
例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的。
1 / 2 2 / / 3 4 4 3
class Solution { public: bool dfs(TreeNode* left, TreeNode* right) { if (left == nullptr && right == nullptr) return true; if (!left || !right) return false; if (left->val != right->val){ return false; } else { return dfs(left->left, right->right) && dfs(left->right, right->left); } } bool isSymmetric(TreeNode* root) { return dfs(root, root); } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/symmetric-tree
【LeetCode #814】二叉樹剪枝
給定二叉樹根結點 root ，此外樹的每個結點的值要麼是 0，要麼是 1。
返回移除了所有不包含 1 的子樹的原二叉樹。
( 節點 X 的子樹為 X 本身，以及所有 X 的後代。)
示例1: 輸入: [1,null,0,0,1] 輸出: [1,null,0,null,1]
解題思路：
遍歷的查找每個節點，然後判斷該二叉樹的某個子樹中是否存在節點值為1的數字，如果存在，則對應子樹的根節點置為nullptr，否則就不變化。
class Solution { public: bool containOne(TreeNode* root) { if (root == nullptr) return false; bool ll = containOne(root->left); bool rr = containOne(root->right); if (!ll) { root->left = nullptr; } if (!rr) { root->right = nullptr; } return ll || rr || root->val == ; } TreeNode* pruneTree(TreeNode* root) { containOne(root); return root; } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/binary-tree-pruning
【LeetCode #655】輸出二叉樹
在一個 m*n 的二維字元串數組中輸出二叉樹，並遵守以下規則：
行數 m 應當等於給定二叉樹的高度。 列數 n 應當總是奇數。 根節點的值（以字元串格式給出）應當放在可放置的第一行正中間。根節點所在的行與列會將剩餘空間劃分為兩部分（左下部分和右下部分）。你應該將左子樹輸出在左下部分，右子樹輸出在右下部分。左下和右下部分應當有相同的大小。即使一個子樹為空而另一個非空，你不需要為空的子樹輸出任何東西，但仍需要為另一個子樹留出足夠的空間。然而，如果兩個子樹都為空則不需要為它們留出任何空間。 每個未使用的空間應包含一個空的字元串""。 使用相同的規則輸出子樹。
示例 1: 輸入: 1 / 2 輸出: [["", "1", ""], ["2", "", ""]]
解題思路：
首先求出二叉樹的高度m，進而得到n = pow(1, m)-1; 然後我們二分的進行輸出到二維vector中，使用二分法。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<string>> printTree(TreeNode* root) { int m = getHeight(root); int n = pow(, m) - ; vector<vector<string>> res(m, vector<string>(n, "")); dfsPrint(root, res, , , n-1); return res; } private: int getHeight(TreeNode* node) { if (node == nullptr) return ; return max(getHeight(node->left), getHeight(node->right)) + ; } void dfsPrint(TreeNode* root, vector<vector<string>>& res, int row, int start, int end) { if(!root || (start > end)) return; int mid = start + (end - start) / ; res[row][mid] = to_string(root->val); dfsPrint(root->left, res, row+, start, mid); dfsPrint(root->right, res, row+, mid+, end); } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/print-binary-tree
【LeetCode #98】驗證二叉搜索樹
給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。 假設一個二叉搜索樹具有如下特徵：
- 節點的左子樹只包含小於當前節點的數。
- 節點的右子樹只包含大於當前節點的數。
- 所有左子樹和右子樹自身必須也是二叉搜索樹。
示例 1: 輸入: 2 / 1 3 輸出: true
解題思路：
複習中序遍歷，對二叉樹進行中序遍歷，並使用pre節點儲存當前節點的上一節點，然後保證邊界結果為遞增序列即可！
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isValidBST(TreeNode* root) { stack<TreeNode*> sta; TreeNode* pre = nullptr; TreeNode* cur = root; while(cur != nullptr || !sta.empty()) { if (cur != nullptr) { sta.push(cur); cur = cur->left; }else { cur = sta.top(); sta.pop(); if (pre && (pre->val >= cur->val)) { return false; } pre = cur; cur = cur->right; } } return true; } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/validate-binary-search-tree
【LeetCode #654】最大二叉樹
給定一個不含重複元素的整數數組。一個以此數組構建的最大二叉樹定義如下：
二叉樹的根是數組中的最大元素。
- 左子樹是通過數組中最大值左邊部分構造出的最大二叉樹。
- 右子樹是通過數組中最大值右邊部分構造出的最大二叉樹。
- 通過給定的數組構建最大二叉樹，並且輸出這個樹的根節點。
解題思路：
首先找到最大值，然後構建結點，從最大值位置分成兩個區間，然後分別使用相應的區間構造root的左右子樹，遞歸構造即可！
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* constructMaximumBinaryTree(vector<int>& nums) { if(nums.size() == ) return nullptr; auto it = max_element(nums.begin(), nums.end()); TreeNode* root = new TreeNode(*it); vector<int> ll(nums.begin(), it); vector<int> rr(it+, nums.end()); root->left = constructMaximumBinaryTree(ll); root->right = constructMaximumBinaryTree(rr); return root; } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/maximum-binary-tree
