大纲：
- 二叉树介绍
- 先序/中序/后序 Preorder/inorder/postorder
- 分治算法 Divide & Conquer
- 二叉树的宽度优先遍历
- 二叉树搜索树
翻转二叉树
Homebrew作者Mark Howell面试被Google拒，因为不会翻转二叉树
（额……这也真够惨的……）
翻转二叉树
解题思路：堆二叉树左右链表进行转换，是否有似曾相识的感觉？交换两个值的swap你一定写过吧，对的，就是它，我们将二叉树的左右假想为两个“特殊的值”，然后定义一个tmp用来储存一方交换值，然后交换他们即可，这里提到的“特殊的值”便是递归调用。
示例代码：
/**
* 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;
}
}
二叉树
二叉树，是指对于树中的每个节点而言，至多有左右两个子节点，即任意节点的度小于等于2
二叉树
概念
- 高度：从根节点到某个节点的路径长度称为该节点的层数(level)，根节点为第0层，非根节点的层数是其父节点的层数加1。树的高度定义为该树中层数最大的叶节点的层数加1，即相当于于从根节点到叶节点的最长路径加1。
- 满二叉树(full binary tree)：如果一棵二叉树的任何结点，或者是叶节点，或者左右子树都存在，则这棵二叉树称作满二叉树。
- 完全二叉树(complete binary tree)：如果一棵二叉树最多只有最下面的两层节点度数可以小于2，并且最下面一层的节点都集中在该层最左边的连续位置上，则此二叉树称作完全二叉树。
Binary Tree DFS Traversal
Binary Tree Traversal
二叉树遍历
二叉树遍历中说的前中后序是以根节点为基准的，根节点在前则为前序遍历，在最后则为后序遍历，否则为中序遍历
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?
问题描述：一个按照中序遍历排列的二叉树，找到给定节点的下一个节点
代码示例：
遍历顺序均为“左、中、右”顺序
当我们不知道根节点时
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) {
//当给定节点为空时返回NULL
if (!node) {
return NULL;
}
//当给定节点的右子树存在时，返回右子树的左子树（如果左子树存在的话，否则返回给定节点的右子树）
if (node->right) {
return leftMostNode(node->right);
}
//如果是给定节点在根左子树的末尾，如上图中保存14的节点，那么就遍历返回到根节点
TreeNode *parent = node->parent;
while (parent && !isLeftChild(node, parent)) {
node = parent;
parent = node->parent;
}
return parent;
}
当我们知道根节点时
TreeNode *inOrderSuccessor(TreeNode *node, TreeNode *root)
{
if (!node) {
return NULL;
}
//如果存在右子树，返回右子树的左子树
if (node->right) {
return leftMostNode(node->right);
}
//当root的值小于给定node值，但是下次开始大于node值时，
//successor成功获取我们要寻找的下一个节点的值
TreeNode *successor = NULL;
while (root) {
if (root->val > node->val) {
successor = root;
root = root->left;
} else {
root = root->right;
}
}
return successor;
}
