Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,

  1
 / \
2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.

解析

这道题目不难，用递归很好解决，只要有儿子就要加数字，这里的数字组成方式是旧的树*10+新的数。

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

/**
 * 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:
    int sumNumbers(TreeNode* root) {
        if(!root) return 0;
        int sum=0;
        getSum(root,root->val,sum);
        return sum;
            
    }
    void getSum(TreeNode * root,int number,int &sum){
        if(root->left)
            getSum(root->left,number*10+root->left->val,sum);
        if(root->right)
            getSum(root->right,number*10+root->right->val,sum);
        if(!root->left&&!root->right){
            sum += number;
        }
    }
};

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
Search for a node to remove.
If the node is found, delete the node.
Note: Time complexity should be O(height of tree).

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

    5
   / \
  4   6
 /     \
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / \
  2   6
   \   \
    4   7

解析

这道题目重点分以下几种情况去分析

1. 如果要删除的那个节点存在，且他的左右子树不都存在。那就直接用子树去替代被删除的节点。
2. 如果要删除的节点左右子树都存在的话，正如上面所示的其实有两种解决方案，一种就是拿右子树的最小值去替代，另外一种就是拿左子树的最大值去替代。替代完之后又要删除替代的那个节点（这里逻辑就可以套用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

   /** * 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* deleteNode(TreeNode* root, int key) { if(!root) return NULL; //搜索那个要删除的节点 if(key < root->val){ //在左子树搜 root->left = deleteNode(root->left,key); } else if(key > root->val){ //在右子树搜 root->right = deleteNode(root->right,key); } else { //找到删除节点，而且左右子树只存在一个以下。 if(!root->left||!root->right){ root = (root->left) ? root->left : root->right; }else{ //左右子树都存在 TreeNode* cur; cur = root->right; while(cur->left){ cur = cur->left ; } root->val = cur->val; //删除右子树下用来替换的节点。 root->right = deleteNode(root->right,cur->val); } } return root; } };

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

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

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    //判断两个向量大小是否相等
        if(preorder.size() != inorder.size())
            return NULL;
        int length = preorder.size();
        //传入首尾的索引
        return constructTree(preorder,0,length-1,inorder,0,length-1);
        
    }
    TreeNode* constructTree(vector<int>& preorder,int ps, int pend,vector<int>& inorder ,int is,int iend){
    //边界值判断 超出就表示没有左右树了。
        if(ps>pend || is>iend)
            return NULL;
        TreeNode *root = new TreeNode(preorder[ps]);
        int irootpos;
            for(int i=is;i<=iend;i++){
                if(inorder[i] == root->val){
                    irootpos = i;
                    break;
                }
            }
        //获取中序的左边的长度 表示左子树的大小
        int leftlength = irootpos - is;
        //获取中序的右边的长度 表示右子树的大小
        int rightlength = iend - irootpos;
        //进入递归
        root->left = constructTree(preorder,ps+1,ps+leftlength,inorder,is,irootpos-1);
        root->right = constructTree(preorder,pend-rightlength+1,pend,inorder,irootpos+1,iend);
        //返回根节点
        return root;
               
    }
    
};

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

     _______6______
    /              \
 ___2__          ___8__
/      \        /      \
0      _4       7       9
      /  \
      3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

意思就是找俩个节点的共同祖先。
这是一颗二叉搜索树，解决思路就比较简答。输入参数是根节点和找共同祖先的两个节点。我们就可以让两个节点和root节点做比较。有以下几种情况：

1. 两个节点中一个比根节点大，另一个比根节点小。那么他们的祖先就是root。
2. 两个节点有一个节点等于根节点，那么很显然他们的祖先就是root。
3. 两个节点都比root节点大，那么缩小两个几点的搜索范围，到root的右子树中，然后再和root->right 做比较。
4. 同理，两个节点都比root的节点小，到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

/**
 * 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if((root->val > p->val && root->val< q->val) ||(root->val < p->val && root->val> q->val))
            return root;
        if(root->val == p->val ||root->val== q->val)
            return root;
        if(root->val>p->val&&root->val>q->val)
            return lowestCommonAncestor(root->left,p,q);
        if(root->val<p->val&&root->val<q->val)
            return lowestCommonAncestor(root->right,p,q);
      
        
    }
};

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Subscribe to see which companies asked this question

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/**
 * 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:
    int maxDepth(TreeNode* root) {
        if(root == NULL)
            return 0;
        return max(1+maxDepth(root->left),1+maxDepth(root->right));
    }
};

这道题目就是不断的递归左右子树，父的深度比儿子深度大1，左右儿子深度做比较，得出最大深度。
可以看出递归思想在解决树问题的重要性。

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew),
but you can’t invert a binary tree on a whiteboard so fuck off.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Subscribe to see which companies asked this question
/**
 * 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;
        root->left =  invertTree(root->left);
        root->right =  invertTree(root->right);
        TreeNode *tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        return root;
    }
};

这到题目不难，主要用了递归的思想，反转二叉树就是每个节点下的左右儿子，我们需要从他的最下面开始反转，这里用递归就很合适。

性质

1. 第i层的节点数为 2^(i-1);
2. 深度为k的节点数为2^k-1 (k>=1);
3. n0=n2+1 n0为度为0的节点就是叶节点，n2为度为2的节点
4. n个节点数，则深度为(log2n)+1
5. ①如果i>1,双亲节点就是i/2;②2i>n结点i无左儿子，否则左孩子节点是2i;③2i+1>n则节点没有右孩子，否则右
   孩子为2i+1;

二叉树的遍历

二叉树有前序遍历，中序遍历和后续遍历。

如上图所示的一棵二叉树，对应的遍历结果分别是：

1. 前序（NLR）：A B D C E G H F I
2. 中序（LNR）：D B A G E H C F I
3. 后序（LRN）：D B G H E I F C A
4. 层序：A B C D E F G H I

按照程序的思想去理解这三种遍历

前序遍历

1
2
3
4
5
6
7

void preOrderTraverse(Bitree T){
   if(T == NULL)
       return;
   printf("%d",T->val);
   preOrderTraverse(T->lchild);//先序遍历左子树
   preOrderTraverse(T->rchild);//先序遍历右子树
}

中序遍历

1
2
3
4
5
6
7

void preOrderTraverse(Bitree T){
   if(T == NULL)
       return;
   preOrderTraverse(T->lchild);//中序遍历左子树
   printf("%d",T->val);
   preOrderTraverse(T->rchild);//中序遍历右子树
}

后序遍历

1
2
3
4
5
6
7

void preOrderTraverse(Bitree T){
   if(T == NULL)
       return;
   printf("%d",T->val);
   preOrderTraverse(T->lchild);//后序遍历左子树
   preOrderTraverse(T->rchild);//后序遍历右子树
}

推导遍历结果

已知前序遍历为ABCDEF 中序遍历为CBAEDF 求后序遍历结果

因为先序遍历可以知道根节点，中序遍历可以知道左右树。
所以A为根，CB为左子树，EDF为右子树。
CB当中B为根,B为A的左儿子，C为B的儿子，因为在中序遍历中C先打印做C为B的左儿子。
DEF中D为根，E为D的左儿子，F为右儿子。
图1

图2

图3

已知中序是ABCDEFG,后续是BDCAFGE,求先序遍历的结果。

根节点可以通过后续得知，中序知道左右子树，所以可以求出先序。
结果为EACBDGF
注意：前序遍历和后续遍历结果知道不能求出中序，因为两者都是只能得出根节点，左右子树不能确定。

You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

题目就是求和为8的向下的路径数
1，2，3，4，5是连续的五段路程不能跳过。如果想到站点5到达各地有几条路程，5->4->3->2->1 ，5->4->3->2，5->4->3，
5->4，有四条路径。找和为8的路径只是多加了个条件。首先我们以root为节点，向下查找，再以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

/**
 * 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:
    int pathSum(TreeNode* root, int sum) {
        int res = 0;
        if(root == NULL)
            return res;
        return dfs(root,sum)+pathSum(root->left,sum)+pathSum(root->right,sum);
    }
    int dfs(TreeNode* root,int sum){
        int res = 0;
        if(root == NULL)
            return res;
        if(root->val == sum)
            res++;
        res+= dfs(root->left,sum-root->val);
        res+= dfs(root->right,sum-root->val);
        return res;

        
    }
};

这里的深度搜索dfs和下面求平衡二叉树时的depth是类似的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public:
        bool isBalanced(TreeNode* root) {
            if(root == NULL)
                return true;
            if(root->left == NULL&&root->right == NULL)
                return true;
            if(abs(depth(root->left)-depth(root->right))>1)
                return false;
            return isBalanced(root->left)&&isBalanced(root->right);
        }
        int depth(TreeNode* root){
            if(root == NULL)
                return 0;
            return max(1+depth(root->left),1+depth(root->right));
        }
    };

判断是否是平衡二叉树

QuestionEditorial Solution My Submissions
Total Accepted: 147366
Total Submissions: 408360
Difficulty: Easy
Contributors: Admin
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Subscribe to see which companies asked this question

平衡二叉树：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
如何解决这道题目一个思路就是按照递归的思路去做。先去判读根节点的左右两边的深度差是否大于1，小于的话再去判断他的子树是否为平衡二叉树。这里就要借助递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public:
        bool isBalanced(TreeNode* root) {
            if(root == NULL)
                return true;
            if(root->left == NULL&&root->right == NULL)
                return true;
            if(abs(depth(root->left)-depth(root->right))>1)
                return false;
            return isBalanced(root->left)&&isBalanced(root->right);
        }
        int depth(TreeNode* root){
            if(root == NULL)
                return 0;
            return max(1+depth(root->left),1+depth(root->right));
        }
    };

一开始我觉得这种算法很顺手的，思考的时候也很简单。但是我后来在leetcode上测了下时间有快20ms，就觉得有问题，原来一看这里又两层递归就是递归里面套递归，所以花费时间很长时间在这里面。
这种算法的时间复杂度为nlogn所以大量时间花费在了算书的深度上。
然后上网查了下有如下的算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        // write code here
        int high=0;
        return isBalance1(root,high);
    }
    bool isBalance1(TreeNode* root,int &high)
    {
        if(root==NULL)
        {
            high=0;
            return true;
        }
        int lhigh,rhigh;
        if(!isBalance1(root->left,lhigh)||!isBalance1(root->right,rhigh))
            return false;
        if(lhigh-rhigh>1||lhigh-rhigh<-1)
            return false;
        high=(lhigh>=rhigh?lhigh:rhigh)+1;
        return true;
    }
};

这种算法就用了一层递归，高度的递归在算平衡里面已经解决了，所以速度要比上面的要快。

Same Tree

Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
Subscribe to see which companies asked this question

题目就是判断两颗树是不是相同的树。
解决思路：依次去判断这棵树的每个节点，是否存在这个节点，每个节点的值是否一样，然后他的子节点是否相同是否遵循以上规则。这就可以用递归来做。
时间复杂度O(n),空间复杂度O(logn)

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

/**
  * 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:
     bool isSameTree(TreeNode* p, 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);
     }
 };