大綱：
- 二叉樹(shù)介紹
- 先序/中序/后序 Preorder/inorder/postorder
- 分治算法 Divide & Conquer
- 二叉樹(shù)的寬度優(yōu)先遍歷
- 二叉樹(shù)搜索樹(shù)
翻轉(zhuǎn)二叉樹(shù)
Homebrew作者M(jìn)ark Howell面試被Google拒守伸，因?yàn)椴粫?huì)翻轉(zhuǎn)二叉樹(shù)
（額……這也真夠慘的……）
翻轉(zhuǎn)二叉樹(shù)
解題思路：堆二叉樹(shù)左右鏈表進(jìn)行轉(zhuǎn)換绎秒，是否有似曾相識(shí)的感覺(jué)？交換兩個(gè)值的swap你一定寫(xiě)過(guò)吧尼摹，對(duì)的见芹，就是它剂娄，我們將二叉樹(shù)的左右假想為兩個(gè)“特殊的值”，然后定義一個(gè)tmp用來(lái)儲(chǔ)存一方交換值玄呛，然后交換他們即可阅懦，這里提到的“特殊的值”便是遞歸調(diào)用。
示例代碼：
/**
* 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* invertTree(TreeNode* root) {
if (root == NULL)
return NULL;
TreeNode* tmpNode = root->left;
root->left = invertTree(root->right);
root->right = invertTree(tmpNode);
return root;
}
}
二叉樹(shù)
二叉樹(shù)徘铝，是指對(duì)于樹(shù)中的每個(gè)節(jié)點(diǎn)而言耳胎，至多有左右兩個(gè)子節(jié)點(diǎn)，即任意節(jié)點(diǎn)的度小于等于2
二叉樹(shù)
概念
- 高度：從根節(jié)點(diǎn)到某個(gè)節(jié)點(diǎn)的路徑長(zhǎng)度稱為該節(jié)點(diǎn)的層數(shù)(level)惕它，根節(jié)點(diǎn)為第0層怕午，非根節(jié)點(diǎn)的層數(shù)是其父節(jié)點(diǎn)的層數(shù)加1。樹(shù)的高度定義為該樹(shù)中層數(shù)最大的葉節(jié)點(diǎn)的層數(shù)加1淹魄，即相當(dāng)于于從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的最長(zhǎng)路徑加1郁惜。
- 滿二叉樹(shù)(full binary tree)：如果一棵二叉樹(shù)的任何結(jié)點(diǎn)，或者是葉節(jié)點(diǎn)揭北，或者左右子樹(shù)都存在扳炬，則這棵二叉樹(shù)稱作滿二叉樹(shù)。
- 完全二叉樹(shù)(complete binary tree)：如果一棵二叉樹(shù)最多只有最下面的兩層節(jié)點(diǎn)度數(shù)可以小于2搔体，并且最下面一層的節(jié)點(diǎn)都集中在該層最左邊的連續(xù)位置上，則此二叉樹(shù)稱作完全二叉樹(shù)半醉。
Binary Tree DFS Traversal
Binary Tree Traversal
二叉樹(shù)遍歷
二叉樹(shù)遍歷中說(shuō)的前中后序是以根節(jié)點(diǎn)為基準(zhǔn)的疚俱，根節(jié)點(diǎn)在前則為前序遍歷，在最后則為后序遍歷缩多，否則為中序遍歷
DFS代碼
//前序遍歷
void preOrderTraversal(TreeNode *root) {
if (!root) {
return;
}
visit(root);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
//中序遍歷
void inOrderTraversal(TreeNode *root) {
if (!root) {
return;
}
inOrderTraversal(root->right);
visit(root);
inOrderTraversal(root->left);
}
//后序遍歷
void postOrderTraversal(TreeNode *root) {
if (!root) {
return;
}
postOrderTraversal(root->left);
postOrderTraversal(root->right);
visit(root);
}
Traverse Iteration
Stack: Preorder
示例代碼：
public static void preOrder(Node root){
LinkedList<Node> stack = new LinkedList<Node>();
Node pointer = root;
stack.push(root);
while(!stack.isEmpty()) {
pointer = stack.pop();
System.out.print(pointer.data+", ");
if(pointer.rightChild != NULL)
stack.push(pointer.rightChild);
if(pointer.leftChild != NULL)
stack.push(pointer.leftChild);
}
System.out.prinln();
}
Find Next in Binary Tree
In-order traverse a binary tree with parent links, find the next node to visit given a specific node.
中序查找
Followup: without parent link?
問(wèn)題描述：一個(gè)按照中序遍歷排列的二叉樹(shù)呆奕，找到給定節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
代碼示例：
遍歷順序均為“左、中衬吆、右”順序
當(dāng)我們不知道根節(jié)點(diǎn)時(shí)
TreeNode *leftMostNode(TreeNode *node) {
if (!node) {
return NULL;
}
while (node->left) {
node = node->left;
}
return node;
}
bool isLeftChild(TreeNode *node, TreeNode *parent) {
return (parent->left == node);
}
TreeNode *inOrderSuccessor(TreeNode *node) {
//當(dāng)給定節(jié)點(diǎn)為空時(shí)返回NULL
if (!node) {
return NULL;
}
//當(dāng)給定節(jié)點(diǎn)的右子樹(shù)存在時(shí)梁钾，返回右子樹(shù)的左子樹(shù)（如果左子樹(shù)存在的話，否則返回給定節(jié)點(diǎn)的右子樹(shù)）
if (node->right) {
return leftMostNode(node->right);
}
//如果是給定節(jié)點(diǎn)在根左子樹(shù)的末尾逊抡，如上圖中保存14的節(jié)點(diǎn)姆泻，那么就遍歷返回到根節(jié)點(diǎn)
TreeNode *parent = node->parent;
while (parent && !isLeftChild(node, parent)) {
node = parent;
parent = node->parent;
}
return parent;
}
當(dāng)我們知道根節(jié)點(diǎn)時(shí)
TreeNode *inOrderSuccessor(TreeNode *node, TreeNode *root)
{
if (!node) {
return NULL;
}
//如果存在右子樹(shù)，返回右子樹(shù)的左子樹(shù)
if (node->right) {
return leftMostNode(node->right);
}
//當(dāng)root的值小于給定node值冒嫡，但是下次開(kāi)始大于node值時(shí)拇勃，
//successor成功獲取我們要尋找的下一個(gè)節(jié)點(diǎn)的值
TreeNode *successor = NULL;
while (root) {
if (root->val > node->val) {
successor = root;
root = root->left;
} else {
root = root->right;
}
}
return successor;
}
