二叉树的遍历

preOrderTraversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };
vector<int> preorderTraversal(TreeNode* root)
{
	vector<int> result;
	stack<TreeNode*> treeNodeStack;
	TreeNode* cursor = root;
	while (cursor || treeNodeStack.size()>0)
	{
		while (cursor)
		{
			result.push_back(cursor->val);
			treeNodeStack.push(cursor);
			cursor = cursor->left;
		}
		cursor = treeNodeStack.top();
		treeNodeStack.pop();
		cursor = cursor->right;
	}
	return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#先序简单
vector<int> preorderTraversal(TreeNode* root) 
{
	vector<int> result;
    if(!root) return result;
    stack<TreeNode*> s;
    TreeNode* cursor = root;
    s.push(root);
    while(!s.empty())
    {
        cursor=s.top();
        result.push_back(cursor->val);
        s.pop();
        if(cursor->right)
        {
            s.push(cursor->right);
        }
        if(cursor->left)
        {
            s.push(cursor->left);
        }
    }
    return result;
}

inOrderTraversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };
vector<int> inorderTraversal(TreeNode* root)
{
	vector<int> result;
	stack<TreeNode*> treeNodeStack;
	TreeNode* cursor = root;
	while (cursor || treeNodeStack.size()>0)
	{
		while (cursor)
		{
			treeNodeStack.push(cursor);
			cursor = cursor->left;
		}
		cursor = treeNodeStack.top();
		result.push_back(cursor->val);
		treeNodeStack.pop();
		cursor = cursor->right;
	}
	return result;
}

只是简单的把先序遍历28行挪了一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
vector<int> postorderTraversal(TreeNode* root)
{
	vector<int> result;
      if(!root)
      {
         return result;
      }
	stack<TreeNode*> treeNodeStack;
	TreeNode* preNode = NULL;
	TreeNode* cursor = root;
	treeNodeStack.push(cursor);
	while (treeNodeStack.size() > 0)
	{
		cursor = treeNodeStack.top();
		if ((!cursor->left && !cursor->right) || (preNode && preNode == cursor->left) ||  (preNode && preNode == cursor->right))
		{
			result.push_back(cursor->val);
			preNode = cursor;
			treeNodeStack.pop();
		}
		else
		{
			if (cursor->right)
			{
				treeNodeStack.push(cursor->right);
			}
			if (cursor->left)
            {
				treeNodeStack.push(cursor->left);
			}
		}
	}
	return result;
}

postOrderTraversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };
vector<int> postorderTraversal(TreeNode* root)
{
	vector<int> result;
      if(!root)
      {
         return result;
      }
	stack<TreeNode*> treeNodeStack;
	TreeNode* preNode = NULL;
	TreeNode* cursor = root;
	treeNodeStack.push(cursor);
	while (treeNodeStack.size() > 0)
	{
		cursor = treeNodeStack.top();
		if ((!cursor->left && !cursor->right) || (preNode && preNode == cursor->left) ||  (preNode && preNode == cursor->right))
		{
			result.push_back(cursor->val);
			preNode = cursor;
			treeNodeStack.pop();
		}
		else
		{
			if (cursor->right)
			{
				treeNodeStack.push(cursor->right);
			}
			if (cursor->left)
            {
				treeNodeStack.push(cursor->left);
			}
		}
	}
	return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#后序拿offer算法
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };
 vector<int> postorderTraversal(TreeNode* root) 
 {
    stack<TreeNode*> s;
    stack<TreeNode*> resultTemp;
    vector<int> result;
    if(!root) return result;
    TreeNode* cursor = root;
    s.push(cursor);
    while(!s.empty())
    {
        cursor=s.top();
        s.pop();
        resultTemp.push(cursor);
        if(cursor->left) s.push(cursor->left);
        if(cursor->right) s.push(cursor->right);
    }
    while(!resultTemp.empty())
    {
        result.push_back(resultTemp.top()->val);
        resultTemp.pop();
    }
    return result;
}

多叉树层序遍历

这个和多叉树的非递归深度重复

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
class Solution
{
public:
    vector <vector<int>> levelOrder(Node *root)
    {
        vector <vector<int>> result;
        if (!root)
        {
            return result;
        }
        queue < Node * > q;
        q.push(root);
        Node *cursor = root;
        vector<int> temp;
        while (!q.empty())
        {
            temp.clear();
            int size = q.size();
            for (int i = 0; i < size; i++)
            {
                cursor = q.front();
                temp.push_back(cursor->val);
                q.pop();
                for (int j = 0; j < cursor->children.size(); j++)
                {
                    q.push(cursor->children[j]);
                }
            }
            result.push_back(temp);
        }
        return result;
    }
};

如果是二叉树只需要两个循环就可以了，因为最内层循环只需要改成左右子树即可

判断子树

输入两棵二叉树A，B，判断B是不是A的子结构。(ps：我们约定空树不是任意一个树的子结构)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
    if(!pRoot1 || !pRoot2) return false;
    bool result = false;
    if(pRoot1->val==pRoot2->val) result = isSubTree(pRoot1,pRoot2);
    if(!result)  result = HasSubtree(pRoot1->left,pRoot2);
    if(!result)  result = HasSubtree(pRoot1->right,pRoot2);
    return result;
}
bool isSubTree(TreeNode* pRoot1,TreeNode* pRoot2)
{
    if(!pRoot2) return true;
    if(!pRoot1) return false; 
    bool result = false;
    if(pRoot1->val==pRoot2->val) result = true;
    if(result) result = isSubTree(pRoot1->left,pRoot2->left);
    if(result) result = isSubTree(pRoot1->right,pRoot2->right);
    return result;
}

需要注意得地方是返回bool判断左树右树的逻辑

多叉树最大深度

题意为输出多叉树最大深度,最容易想到的方式是递归,该题记录重点为第二种非递归方式,其实也相当于多叉树的层序遍历。

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
class Node {
public:
	int val;
	vector<Node*> children;
	Node() {}
	Node(int _val, vector<Node*> _children) {
		val = _val;
		children = _children;
	}
};
int maxDepth(Node* root);
int main()
{
	int maxDepth(Node* root);
	return 0;
}
int maxDepth(Node* root) 
{
    if(!root)//出口条件
    {
        return 0;
    }
    int maxDep=0;
    for(int i =0;i<root->children.size();i++)
    {
        maxDep=max(maxDep,maxDepth(root->children[i]));
    }
    return maxDep+1;
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
class Node {
public:
	int val;
	vector<Node*> children;
	Node() {}
	Node(int _val, vector<Node*> _children) {
		val = _val;
		children = _children;
	}
};
int maxDepth(Node* root);
int main()
{
	int maxDepth(Node* root);
	return 0;
}
int maxDepth(Node* root)
{
    if(!root)//只是当root为空时候的一个判断
    {
        return 0;
    }
	int depth = 0;
	queue<Node*> q;
	q.push(root);
	Node* cursor = NULL;
	while (!q.empty())//这里的三层循环第二层目的是将每一层都组成一个数组,并计算层序,如果单纯为了输出层序遍历的结果完全可以使用两层循环
	{
	    int size = q.size();
	    for (int i = 0; i < size;i++)//注意该队列其实是一层一层从做到右入队列的,切不可用while(!q.empty())
	    {
		    cursor = q.front();
		    q.pop();
		    for (int j = 0; j < cursor->children.size(); j++)
		    {
			    q.push(cursor->children[j]);
		    }
		}
                depth++;//每层加1
	}
    return depth;
}

注意，两个方法中的if(!root)作用并不一样，对于递归而言是跳出条件，而对于非递归而言只是一种情况

二叉树镜像

把一个二叉树变为镜像

1
2
3
4
5
6
7
8
9
10
11
void Mirror(TreeNode *pRoot) 
{
    if(pRoot)
    {
        TreeNode* node = pRoot->left;
        pRoot->left=pRoot->right;
        pRoot->right=node;
        Mirror(pRoot->left);
        Mirror(pRoot->right);
    }
}

对称二叉树

1
2
3
4
5
6
7
8
9
10
11
bool judge(TreeNode* p,TreeNode* q)
{
    if(!p && !q) return true;
    if(!p || !q) return false;
    if(p->val != q->val) return false;
    return judge(p->left,q->right) && judge(p->right,q->left);
}
bool isSymmetrical(TreeNode* pRoot)
{
    return judge(pRoot,pRoot);
}

树的子结构(或子树)

给定两棵二叉树A和B，判断A是不是B的子结构或子树，子结构要求A是B的一部分即可，但是子树要求叶子结点也得相同.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool judgeSubTree(TreeNode *pRoot1, TreeNode *pRoot2)
{
    //判断子结构
    if (!pRoot2) return true;
    if (!pRoot1) return false;
    //判断子树
    //if (!pRoot1 && !pRoot2) return true;
    //if (!(pRoot1 && pRoot2)) return false;
    bool judge = pRoot1->val == pRoot2->val;
    if (judge) judge = judgeSubTree(pRoot1->left, pRoot2->left);
    if (judge) judge = judgeSubTree(pRoot1->right, pRoot2->right);
    return judge;
}

bool isSubtree(TreeNode *pRoot1, TreeNode *pRoot2)
{
    if (!pRoot1 || !pRoot2) return false;
    bool judge = judgeSubTree(pRoot1, pRoot2);
    if (!judge) judge = isSubtree(pRoot1->left, pRoot2);
    if (!judge) judge = isSubtree(pRoot1->right, pRoot2);
    return judge;
}

二叉树中路径和

输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
vector<vector<int>> result;
void FindPath(TreeNode* root,int expectNumber,vector<int>& path)
{
    if(!root) return;
    path.push_back(root->val);
    expectNumber-=root->val;
    if(!root->left && !root->right && !expectNumber)
    {
        result.push_back(path);
    }
    if(root->left)
    {
        FindPath(root->left,expectNumber,path);   
    }
    if(root->right)
    {
        FindPath(root->right,expectNumber,path);   
    }
    path.pop_back();
}
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) 
{
    if(!root) return result;
    vector<int> path;
    FindPath(root,expectNumber,path);
    return result;
}

二叉树所有路径中和最大

这里的路径指的是树上所有能联通的两个节点之间的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int maxSumResult = 0;

int maxPathSum(TreeNode *root)
{
    if (!root)
        return 0;
    int left = maxPathSum(root->left);
    int right = maxPathSum(root->right);
    int temp = root->val;
    if (left > 0)
    {
        temp += left;
    }
    if (right > 0)
    {
        temp += right;
    }
    maxSumResult = max(maxSumResult, temp);
    return max(root->val, max(root->val + left, root->val + right));
}

调用maxPathSum后maxSumResult得到的就是最大路径和

判断是不是平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int getHeight(TreeNode* root,bool& ifBalance)
{
    if(!root) return 0;
    int left = getHeight(root->left,ifBalance);
    int right =getHeight(root->right,ifBalance);
    if(abs(left-right)>1)
    {
        ifBalance=false;
    }
    return left>right?left+1:right+1;
}
bool IsBalanced_Solution(TreeNode* pRoot) 
{
    bool ifBalance=true;
    getHeight(pRoot,ifBalance);
    return ifBalance;
}

next指针

完全二叉树增加next指针指向右侧节点

只适用于完全二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Node *connectCore(Node *root)
{
    if (!root->left && !root->right) return NULL;
    root->left->next = root->right;
    connectCore(root->left);
    if (root->next)
    {
        root->right->next = root->next->left;
    }
    connectCore(root->right);
    return root;
}

Node *connect(Node *root)
{
    if (!root || (!root->left && !root->right))
        return root;
    return connectCore(root);
}

层序遍历，适用于任何形式的二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Node *connect(Node *root)
{
    if(!root ||(!root->left && !root->right)) return root;
    Node *cursor = root;
    queue<Node *> q;
    q.push(cursor);
    while (!q.empty())
    {
        int size = q.size();
        for (int i = 0; i < size; ++i)
        {
            cursor = q.front();
            q.pop();
            cursor->next = (i==size-1)? nullptr:q.front();
            if(cursor->left)
            {
                q.push(cursor->left);
            }
            if(cursor->right)
            {
                q.push(cursor->right);
            } 
        }
    }
    return root;

二叉树从右向左看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void fromRight(TreeNode* root,vector<int>& result,int deep)
    {
        if(!root)
        {
            return;
        }
        if(deep==result.size())
        {
            result.push_back(root->val);
        }
        fromRight(root->right,result,deep+1);
        fromRight(root->left,result,deep+1);
    }
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        fromRight(root,result,0);
        return result;
    }

这是用中右左的方式遍历,若从左向右看可以中左右的方式遍历

找到最近公共祖先

1
2
3
4
5
6
7
8
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
{
    if (root == NULL || root == p || root == q) return root;
    TreeNode *left = lowestCommonAncestor(root->left, p, q);
    TreeNode *right = lowestCommonAncestor(root->right, p, q);
    if (left != NULL && right != NULL) return root;
    return left == NULL ? right : left;
}

二叉树最大宽度

还不知道咋解决溢出问题…先这样

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int widthOfBinaryTree(TreeNode *root)
{
    if (!root) return 0;
    queue<TreeNode *> q;
    q.push(root);
    unordered_map<TreeNode *, int> record;
    record[root] = 1;
    int result = 1;
    while (!q.empty())
    {
        TreeNode *leftNode = q.front();
        int leftEdge = record[leftNode];
        int size = q.size();
        for (int i = 0; i < size; ++i)
        {
            TreeNode *currentNode = q.front();
            q.pop();
            result = max(result, record[currentNode] - leftEdge + 1);
            if (currentNode->left)
            {
                q.push(currentNode->left);
                record[currentNode->left] = 2 * record[currentNode];
            }
            if (currentNode->right)
            {
                q.push(currentNode->right);
                record[currentNode->right] = 2 * record[currentNode] + 1;
            }
        }
    }
    return result;
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int result = 0;

void DFS(TreeNode *root, int level, int order, unordered_map<int, int> record)
{
    if (!root) return;
    if (record.find(level) == record.end())
    {
        record[level] = order;
    }
    result = max(result, order - record[level] + 1);
    DFS(root->left, level + 1, order * 2, record);
    DFS(root->right, level + 1, order * 2 + 1, record);
}

int widthOfBinaryTree(TreeNode *root)
{
    if (!root) return 0;
    unordered_map<int, int> record;
    DFS(root, 0, 1, record);
    return result;
}

判断二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
   bool isValidDFS(TreeNode *root, long low, long high)
{
    if (!root) return true;
    if (root->val > low && root->val < high)
    {
        bool result = isValidDFS(root->left, low, root->val);
        if (result)
        {
            result = isValidDFS(root->right, root->val, high);
        }
        return result;
    }
    return false;
}

bool isValidBST(TreeNode *root)
{
    return isValidDFS(root, LONG_MIN, LONG_MAX);
}

更大的二茬搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int currVal = 0;

void helper(TreeNode *root)
{
    if (root)
    {
        helper(root->right);
        root->val += currVal;
        currVal = root->val;
        helper(root->left);
    }
}

TreeNode *bstToGst(TreeNode *root)
{
    helper(root);
    return root;
}

判断完全二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 bool isCompleteTree(TreeNode *root)
{
    if (!root)
        return true;
    queue<TreeNode *> record;
    record.push(root);
    bool flag = true;
    while (!record.empty())
    {
        TreeNode *front = record.front();
        record.pop();
        if (!flag && (front->left || front->right))
        {
            return false;
        }
        if(front->left && front->right)
        {
            record.push(front->left);
            record.push(front->right);
        } else if (front->right)
        {
            return false;
        } 
        else if (front->left)
        {
            flag = false;
            record.push(front->left);
        } else
        {
            flag = false;
        }
    }
    return true;
}

二叉树中序遍历的前驱和后继

前驱:

1.如果当前节点有左子树则找左子树的最右
2.如果当前节点没有左子树则找其父节点，直到某节点是父节点的右子树，返回该父节点

1
2
3
4
5
6
7
8
9
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};

后继

1.如果当前节点右右子树则找右子树的最左
2.如果当前节点没有右子树则找其父节点，直到该某节点是父节点的左子树，返回该父节点.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct TreeLinkNode
{
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {  }
}
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if(pNode ==nullptr)
            return nullptr;
        // 假如有右子树，就去找右子树的最左节点
        if(pNode->right){   
            TreeLinkNode * res=pNode->right;
            while(res->left)
                res=res->left;
            return res;
        }
        //没有右子树时，就一直向上找，找到当前节点是父节点的左孩子为止
        TreeLinkNode *father=pNode->next;
        TreeLinkNode * cur=pNode;
        while(father != nullptr && father->left != cur){
            cur=father;
            father=father->next;
        }
        return father;
    }