LeetCode二叉树基础题（不断更新）_判断树是否有异常边 leetcode

107.Binary Tree Level Order Traversal II

题意：
给定一个二叉树，由下而上、由左向右遍历其节点值并存储进一个二维vector里。

思路：
广度优先遍历，最后再将二维vector颠倒即可。每遍历一层将该层的所有孩子节点放进队列里，放进去的的节点恰好是下一层节点总数，以此辨识节点所属层数。

/**
 * 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:

    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        if(root==NULL) return ans;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            vector<int> thislayer;
            int l=q.size();
            for(int i=0;i<l;i++)
            {
                TreeNode* t=q.front();
                thislayer.push_back(t->val);
                q.pop();
                if(t->left!=NULL) q.push(t->left);
                if(t->right!=NULL) q.push(t->right);
            }
            ans.push_back(thislayer);
        }
        reverse(ans.begin(), ans.end());
        return ans;   
    }
};
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

类似的题还有199、103、515，代码相似度>90%

101. Symmetric Tree

题意：判断一棵树是否对称。

思路：
使用递归和层次遍历。从根节点开始递归地比较左右子树是否相同，在这个过程中如果左右子树节点值不相等，或者有一方为空另一方不为空，则返回false，否则继续递归下去。最后返回true。

110. Balanced Binary Tree

题意：判断一棵树是否平衡

思路：
利用递归思想。
一棵树是否平衡取决于左子树与右子树是否都平衡；
一棵树的高度等于左右子树中高度大的子树的高度加一。

98. Validate Binary Search Tree

题意：判断一棵树是否是二叉搜索树

思路：
中序遍历得到一个序列，如果序列是升序列，说明这棵树是二叉搜索树。

236. Lowest Common Ancestor of a Binary Tree

题意：求一棵树中两个节点的最低共同祖先

思路：
分别记录从根节点到达两个节点的两条路径，比较两条路径，不相同的上一个节点就是最低公共祖先。

257. Binary Tree Paths

题意：打印出所有从根到叶节点的路径

思路：深度优先搜索，遇到叶节点即输出路径；注意回退时要正确地从栈中抛出节点。

class Solution {
public:

    void getString(vector<TreeNode*>& path,vector<string>& ans)
    {
        int l=path.size();
        string s;
        for(int i=0;i<l;i++)
        {
            if(i!=l-1)
                s+=to_string(path[i]->val)+"->";
            else s+=to_string(path[i]->val);
        }
        ans.push_back(s);
    }


    void GetNodePath(TreeNode* root, vector<TreeNode*>& path,vector<string>& ans)  
    {  
        path.push_back(root);  

        if(!root->left && !root->right)
        {getString(path,ans);return ;} 

        if(root->left)  
            {GetNodePath(root->left, path,ans);  path.pop_back();}
        if(root->right)  
            {GetNodePath(root->right, path,ans);  path.pop_back();}
    }  


    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans;
        if(root==NULL) return ans;
        vector<TreeNode*> path;
        GetNodePath(root,path,ans);
        return ans;
    }
};
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

类似的题还有129（对根到叶节点所有路径数字求和）、112（判断是否存在一条路径求和等于给定数字）、113（输出所有路径求和等于给定数字的路径）。