二叉樹的前、中、后序遍歷

1.前序遍歷：先訪問根節點，再訪問左子樹，最后訪問右子樹
根 左 右
2.中序遍歷：先訪問左子樹，再訪問根，最后訪問右子樹
左 根 右
3.后序遍歷：先訪問左子樹，再訪問右子樹，最后訪問根
左 右 根

N 表示 NULL
前序訪問順序：1 2 3 N N N 4 5 N N 6 N N
中序訪問順序：N 3 N 2 N 1 N 5 N 4 N 6 N
后序訪問順序：N N 3 N 2 N N 5 N N 6 4 1

求二叉樹第K層節點的個數

子問題是：root不為空，k不等于1
轉化為求左子樹加右子樹第三層的節點個數
每層k都減1，如果該層有root == NULL就返回0

//求二叉樹第k層的節點個數 
int TreeLevelKSize(BTNode* root,int k)
{if (root == NULL)return 0;if (k == 1)return 1;return TreeLevelKSize(root->left, k-1) + TreeLevelKSize(root->right, k-1);
}

二叉樹查找值為x的節點

找到一個值為x的節點就返回，因為函數只有一個返回值
return 只能返回給上一層
如果找到了不存入一個變量中，找到的值就會重復找（后面會丟失找到的值）

//二叉樹查找值為x的節點
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->val == x)return root;//只能返回給它的上一層//前序遍歷BTNode* ret1 = TreeFind(root->left, x);if (ret1)return ret1;BTNode* ret2 = TreeFind(root->right, x);if (ret2)return ret2;//都沒找到return NULL;
}

leetcode相同的樹

思路：
比較兩棵樹的根，左子樹和右子樹是否相等
1.兩棵樹的根都為NULL,返回true
2.其中一棵樹的根為NULL,兩樹的節點不相同返回false
3.兩樹的根都不為NULL,比較兩樹的根的值
4.子問題：遍歷兩樹的左子樹和右子樹（比較左根和右根）

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{if(p == NULL&&q == NULL)return true;//其中一個節點為空，另一個節點不為空，返回falseif(p == NULL || q == NULL)return false;//兩個節點都不為空if(p->val != q->val)return false;return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

對稱二叉樹

思路：
這題和上一題很想，可以理解為鏡像二叉樹（即一棵樹的左子樹和右子樹要一樣，一棵樹的右子樹和左子樹要一樣）

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
bool _isSymmetric(struct TreeNode* p,struct TreeNode* q)
{if(p == NULL&&q == NULL)return true;if(p == NULL||q == NULL)return false;if(p->val != q->val)return false;return _isSymmetric(p->left,q->right)&&_isSymmetric(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root) 
{return _isSymmetric(root->left,root->right);
}

二叉樹的前序遍歷

思路：
1.先算出二叉樹中有多少個節點，再開辟這么多個節點
這樣不會造成空間不足或空間浪費
2.i 是數組的下標，要用指針傳遞過去，不用指針的話，形參i的改變不會影響實參i,可能會覆蓋前面的值

3.前序遍歷，如果有節點就把節點中的值放入數組中，如果沒有就返回NULL,遵循根左右依次把值放入數組中

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/
//算出樹的節點個數
int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//前序遍歷
void preorder(struct TreeNode* root,int* arr,int* pi)
{if(root == NULL)return;arr[(*pi)++] = root->val;preorder(root->left,arr,pi);preorder(root->right,arr,pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{*returnSize = TreeSize(root);int* arr = (int*)malloc(sizeof(int)*(*returnSize));//前序遍歷int i = 0;//下標是一個小坑，如果不用指針，每次遞歸調用i的值是形參有時會覆蓋前面的值preorder(root,arr,&i);return arr;
}

另一棵子樹

思路：
1.root在走，直到root == NULL都沒找到值和subRoot相同的節點，那么就返回false
2.如果能找到和root相同的節點，那么比較root后面的節點（子樹中）是否和subRoot相同
3.只要找到一個子樹是和subRoot相同的那么就返回true

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*///這里面子樹與另一題兩個子樹是否相同有一樣的邏輯
bool issametree(struct TreeNode* p,struct TreeNode* q)
{if(p == NULL&&q == NULL)return true;if(p == NULL || q == NULL)return false;if(p->val != q->val)return false;return issametree(p->left,q->left) && issametree(p->right,q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{//subRoot不為空,使用root在遞歸，所以root可能會走到空false//subRoot至少有一個節點if(root == NULL)return false;if(root->val == subRoot->val&&issametree(root,subRoot))return true;//root在走，subRoot不走，之后利用root和subRoot相等的節點，再用issametree比較是否是子樹return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

牛客 二叉樹的遍歷

思路：
總體來說是先開一個100個字符的字符串數組，然后構建節點，最后中序遍歷打印數組
1.構建節點時要注意如果root == ‘#’時，不能在判斷的時候（*pi）++,如果它不是‘#’的話還++就跳過一個字符了
2.開1個節點的樹，就把數組中的值放入樹中，然后為左樹和右樹開辟一個節點，最后返回根節點，把各個節點鏈接起來，return root是為了鏈接節點

#include <stdio.h>
#include<stdlib.h>typedef struct TreeNode
{ struct TreeNode* left;struct TreeNode* right;int val;
}TreeNode;
//構建節點
TreeNode* CreatTree(char* a,int* pi)
{if(a[*pi] == '#'){(*pi)++;return NULL;}//非空TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));root->val = a[(*pi)++];//下面這里沒有想出來,遞歸root的左邊創建一個節點,//然后遞歸root的右邊創建一個節點，//最后返回根，鏈接起來root->left = CreatTree(a,pi);root->right = CreatTree(a,pi);return root;
}
//中序遍歷
void order(TreeNode* root)
{if(root == NULL)return;order(root->left);printf("%c ",root->val);order(root->right);
}
int main() 
{char a[100];scanf("%s",a);int i = 0;TreeNode* ret = CreatTree(a,&i);order(ret);return 0;
}