自己之前學過關于二叉樹的一些東西，但是時間有點久自己已經忘完了，最近在刷leetcode上的題目的時候感覺已經忘完了，回頭又看了一邊簡單的寫一點自己的筆記吧
常見的二叉樹型別有：
- 斜樹：在一個二叉樹中僅有左數或者僅有右樹的情況為斜樹
- 滿二叉樹：在一棵二叉樹中所有的節點都具有左子樹和右子樹，且所有的葉節點都位于同一層上
- 完全二叉樹：按照從左到右，從上到下的的方法對一個二叉樹編號，沒有出現數字中斷的情形
今天在書體中，遇到了一個新的概念叫做二叉搜索樹：
二叉查找樹（Binary Search Tree），（又：二叉搜索樹，二叉排序樹）
它或者是一棵空樹，或者是具有下列性質的二叉樹：
1. 若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
2. 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
3. 它的左、右子樹也分別為二叉排序樹，
題目如圖所示
自己參考大佬的博客得到了啟發寫出的解答，利用中序遍歷發，然后使用逆中序遍歷就可以實作對問題的求解
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 int num = 0; 12 public: 13 TreeNode* convertBST(TreeNode* root) { 14 if(root == NULL) 15 return NULL; 16 convertBST(root->right); 17 root->val = root->val+num; 18 num = root->val; 19 convertBST(root->left); 20 return root; 21 22 } 23 };
同時自己也去回看了之前的遍歷一顆二叉樹的演算法——利用遞回的方法（前序，中序，后續）對一棵樹實作遍歷，加深了對演算法進行變體的應用理解，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/101256.html
標籤：其他
上一篇：TCP資料復制到另一臺服務器