算法经典面试题（5）——二叉树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法经典面试题（5）——二叉树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含15879字，纯文字阅读大概需要23分钟。

内容图文

*题目编号为Leetcode中对应的题号。
某位大佬的Leetcode题解参考链接

二叉树

完全二叉树：除了最后一层，所有层的节点数达到最大，最后一层的所有节点在最左侧。（堆就是二叉树）
满二叉树：所有层的节点数达到最大。
平衡二叉树：没一个节点的左右子树的高度差不超过1.
二分搜索树：每个节点的键值大于左孩子、小于右孩子，以左右孩子为根的子树仍然为二分搜索树。
二分搜索树中的一个节点大于其右子树中的所有节点，小于其左子树中的所有节点。

具有天然递归条件

    // 前序遍历
    void preorder(TreeNode* node){
        if(node == NULL)				// 递归终止条件
            return;
        
        cout<<node->val<<endl;			// 递归过程
        preorder(node->left);
        preorder(node->right);
    }

无非是广度优先遍历和深度优先遍历；与高度有关、有路径有关

(104二叉树的最大深度) 给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

    int maxDepth(TreeNode* root) {
        if(root==NULL)
        return 0;
        
        int depth_l=0, depth_r=0;
        if(root->left)
            depth_l=maxDepth(root->left);
        if(root->right)
            depth_r=maxDepth(root->right);
    
        return max(depth_l,depth_r)+1;
    }

(111二叉树的最小深度) 给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

    class Solution {
    public:
        int minDepth(TreeNode* root) {
    
            if(root == NULL)
                return 0;
    
            if(root->left == NULL && root->right == NULL)
            return 1;
    
        int ret = INT_MAX;
            if(root->left)
                ret = min(ret, 1 + minDepth(root->left));
            if(root->right)
                ret = min(ret, 1 + minDepth(root->right));
            return ret;
        }
    };

(226翻转二叉树) 翻转一棵二叉树。

示例：

输入：
     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：
     4
   /   \
  7     2
 / \   / \
9   6 3   1

    TreeNode* invertTree(TreeNode* root) {
    	if(root==NULL)
            return NULL;
        
        invertTree(root->left);
        invertTree(root->right);
        swap(root->left,root->right);
        return root;
    }

(100相同的二叉树) 给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

    class Solution {
    public:
        bool isSameTree(TreeNode* p, TreeNode* q) {
    
            if(!p && !q) return true;
            if(!p || !q) return false;
            if(p->val != q->val) return false;
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        }
    };

(102二叉树的层序遍历)

    // 基础层序遍历
    // 使用队列实现BFS
    vector<int> levelOrder(TreeNode* root) {
        vector<int> ret;
        if (root == NULL)
            return ret;
    
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty())
        {
            TreeNode* node = q.front();
            ret.push_back(node->val);
            q.pop();
    
            if (node->left)
                q.push(node->left);
            if (node->right)
                q.push(node->right);
        }
        return ret;
    }
    // 使用队列实现
    vector<vector<int>> levelOrder(TreeNode* root) {
    
        vector<vector<int>> res;
        if(root == NULL)
            return res;
    
        queue<pair<TreeNode*,int>> q;
        q.push(make_pair(root, 0));
    
        while(!q.empty()){
    
            TreeNode* node = q.front().first;
            int level = q.front().second;
            q.pop();
    
            if(level == res.size())
                res.push_back(vector<int>());
            assert( level < res.size() );
    
            res[level].push_back(node->val);
            if(node->left)
                q.push(make_pair(node->left, level + 1 ));
            if(node->right)
                q.push(make_pair(node->right, level + 1 ));
        }
    
        return res;
    }
    // 使用递归实现
    class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            vector<vector<int>> ans;
            pre(root, 0, ans);
            return ans;
        }
        
        void pre(TreeNode *root, int depth, vector<vector<int>> &ans) {
            if (!root) return ;
            if (depth >= ans.size())
                ans.push_back(vector<int>());
            ans[depth].push_back(root->val);
            pre(root->left, depth + 1, ans);
            pre(root->right, depth + 1, ans);
        }
    };

(101对称二叉树) 给定一个二叉树，检查它是否是镜像对称的。

    // Recursive
    class Solution {
    public:
        bool isSymmetric(TreeNode* root) {
    
            if(root == NULL)
                return true;
    
            return is_mirror(root, root);
        }
    
    private:
        bool is_mirror(TreeNode* root1, TreeNode* root2){
    
            if(root1 == NULL && root2 == NULL)
                return true;
    
            if(root1 == NULL || root2 == NULL)
                return false;
    
            if(root1->val != root2->val)
                return false;
    
            return is_mirror(root1->left, root2->right) &&
                   is_mirror(root1->right, root2->left);
        }
    };
    
    /// Non-Recursive
    /// Using two queues to level traverse the root in different directions
    /// 利用队列实现BFS（层序遍历）
    /// Time Complexity: O(n)
    /// Space Complexity: O(n)
    class Solution {
    public:
        bool isSymmetric(TreeNode* root) {
    
            if(root == NULL)
                return true;
    
            queue<TreeNode*> q1, q2;
            q1.push(root);
            q2.push(root);
            while(!q1.empty() && !q2.empty()){
                TreeNode* node1 = q1.front();
                q1.pop();
    
                TreeNode* node2 = q2.front();
                q2.pop();
    
                if(node1 == NULL && node2 == NULL)
                    continue;
    
                if(node1 == NULL || node2 == NULL)
                    return false;
    
                if(node1->val != node2->val)
                    return false;
    
                q1.push(node1->left);
                q1.push(node1->right);
    
                q2.push(node2->right);
                q2.push(node2->left);
            }
    
            return q1.empty() && q2.empty();
        }
    };

(222完全二叉树的节点个数) 给出一个完全二叉树，求出该树的节点个数。

示例:

输入: 
    1
   / \
  2   3
 / \  /
4  5 6
输出: 6

    // 常规解法：BFS或DFS
    // 法一：使用队列进行BFS
    // 法二：使用DFS
    class Solution {
    public:
        int countNodes(TreeNode* root) {
            if (root == NULL)
                return 0;
    
            countNodes(root->left);
            countNodes(root->right);
            return ++count;
        }
    private:
        int count=0;
    };
    /// Recursion
    /// Time Complexity: O(h^2) where h is the height of the tree
    /// Space Complexity: O(h)
    class Solution {
    
    public:
        int countNodes(TreeNode* root) {
    
            if(root == NULL)
                return 0;
    
            int leftLeft = leftHeight(root->left);
            int leftRight = rightHeight(root->left);
            if(leftLeft == leftRight)
                return 1 + ((1<<leftLeft) - 1) + countNodes(root->right);
    
            assert(leftLeft == leftRight + 1);
            return 1 + ((1<<leftRight) - 1) + countNodes(root->left);
        }
    
    private:
        int leftHeight(TreeNode* root){
            if(root == NULL)
                return 0;
            return 1 + leftHeight(root->left);
        }
    
        int rightHeight(TreeNode* root){
            if(root == NULL)
                return 0;
            return 1 + rightHeight(root->right);
        }
    };

(110平衡二叉树) 给定一个二叉树，判断它是否是高度平衡的二叉树。

示例:

    3
   / \
  9  20
    /  \
   15   7
返回true
       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回false

    class Solution {
    public:
        bool isBalanced(TreeNode* root) {
            return height(root) != -1;
        }
        // 返回树的高度 -1为不平衡
        int height(TreeNode* root){
            if(root == nullptr)
                return 0;
            int left = height(root->left);
            if(left == -1) 
                return -1;
            int right = height(root->right);
            if(right == -1)
                return -1;
            return abs(left - right) > 1 ? -1 : 1 + max(left, right);
        }
    };

(404左叶子之和) 计算给定二叉树的所有左叶子之和。

示例：

    3
   / \
  9  20
    /  \
   15   7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

    class Solution {
    
    private:
        int res = 0;
    
    public:
        int sumOfLeftLeaves(TreeNode* root) {
    
            if(!root) return 0;
    
            dfs(root, false);
            return res;
        }
    
    private:
        void dfs(TreeNode* node, bool isLeft){
    
            if(!node->left && !node->right){
                if(isLeft) res += node->val;
                return;
            }
    
            if(node->left) dfs(node->left, true);
            if(node->right) dfs(node->right, false);
        }
    };

(257二叉树的所有路径) 给定一个二叉树，返回所有从根节点到叶子节点的路径。

   输入:
      1
    /   \
   2     3
    \
     5
   输出: ["1->2->5", "1->3"]
   解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

    vector<string> binaryTreePaths(TreeNode* root) {

    vector<string> res;

    if(root == NULL)
        return res;
	
    // 如果是叶子节点
    if(root->left == NULL && root->right == NULL){
        res.push_back(to_string(root->val));
        return res;
    }

    // 找到左子树的所有路径
    vector<string> leftPaths = binaryTreePaths(root->left);
    for(int i = 0 ; i < leftPaths.size() ; i ++)
        res.push_back(to_string(root->val) + "->" + leftPaths[i]);

    // 找到右子树的所有路径
    vector<string> rightPaths = binaryTreePaths(root->right);
    for(int i = 0 ; i < rightPaths.size() ; i ++)
        res.push_back(to_string(root->val) + "->" + rightPaths[i]);

    return res;
}

// 存储为数组
vector<vector<int>> binaryTreePaths2(TreeNode* root) {
    vector<vector<int>> ret;
    if (root == NULL)
        return ret;

    vector<int> tres;
    dfs(root, tres, ret);
    return ret;
}
void dfs(TreeNode* node, vector<int>& tres, vector<vector<int>>& ret)
{
    tres.push_back(node->val);

    if (!node->left && !node->right)
        ret.push_back(tres);

    if (node->left)
        dfs(node->left, tres, ret);
    if (node->right)
        dfs(node->right, tres, ret);

    tres.pop_back();
    return;
}

(112路径总和) 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

示例:
给定如下二叉树，以及目标和 sum = 22，

  		  5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

bool hasPathSum(TreeNode* root, int sum) {
    if(root==NULL)
        return false;
    
    if(root->val==sum && !root->left && !root->right)
        return true;
    
    if(root->left && hasPathSum(root->left, sum-root->left->val))
        return true;
        
    if(root->right && hasPathSum(root->right, sum-root->right->val))
        return true;
    
    return false;
}
// 法二：
bool hasPathSum(TreeNode* root, int sum) {
    if (root == NULL)
        return false;

    return dfs(root, 0, sum);
}

bool dfs(TreeNode* node, int tsum, int sum)
{
    tsum += node->val;

    if (!node->left && !node->right)
    {
        if (tsum == sum)
            return true;
    }

    if (node->left && dfs(node->left, tsum, sum))
        return true;
    if (node->right && dfs(node->right, tsum, sum))
        return true;


    tsum -= node->val;
    return false;
}

(113路径总和II) 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
示例
给定如下二叉树，以及目标和 sum = 22，

       5
      / \
     4   8
    /   / \
   11  13  4
  /  \    / \
 7    2  5   1

 [
    [5,4,11,2],
    [5,8,4,5]
 ]

 class Solution {
 
 public:
     vector<vector<int>> pathSum(TreeNode* root, int sum) {
 
         vector<vector<int>> res;
         if(!root)
             return res;
 
         vector<int> tres;
         dfs(root, tres, 0, sum, res);
         return res;
     }
 
 private:
     void dfs(TreeNode* node, vector<int>& tres, int tsum,
              int sum, vector<vector<int>>& res){
 
         tres.push_back(node->val);
         tsum += node->val;
 
         if(!node->left && !node->right){
             if(tsum == sum)
                 res.push_back(tres);
         }
         if (node->left)
             dfs(node->left, tres, tsum, sum, res);
 
         if (node->right)
             dfs(node->right, tres, tsum, sum, res);
 
         tres.pop_back();
         return;
     }
 };

(129求根到叶子节点数字之和) 给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

示例:

输入: [1,2,3]
    1
   / \
  2   3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.

输入: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
输出: 1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495.
从根到叶子节点路径 4->9->1 代表数字 491.
从根到叶子节点路径 4->0 代表数字 40.
因此，数字总和 = 495 + 491 + 40 = 1026.

class Solution {
public:
    int sumNumbers(TreeNode* root) {

        if(!root) return 0;

        int res = 0;
        dfs(root, 0, res);
        return res;
    }

private:
    void dfs(TreeNode* node, int tnum, int& sum){

        tnum = tnum * 10 + node->val;

        if(!node->left && !node->right)
            sum += tnum;
        else{
            if(node->left)
                dfs(node->left, tnum, sum);
            if(node->right)
                dfs(node->right, tnum, sum);
        }
    }
};

(437 路径总和III) 给定一个二叉树，它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
```
 root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
     
     	  10
          /  \
         5   -3
        / \    \
       3   2   11
      / \   \
     3  -2   1
     
     返回 3。和等于 8 的路径有:
     
     1.  5 -> 3
     2.  5 -> 2 -> 1
     3.  -3 -> 11
```
(235 二分搜索树的最近公共祖先) 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

算法经典面试题（5）——二叉树 - 文章图片
示例:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

说明:

所有节点的值都是唯一的。

p、q 为不同节点且均存在于给定的二叉搜索树中。

// 定义：在以root为根节点的二分搜索树中，找到节点p和q的最近公共祖先节点
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(root==NULL || p==NULL || q==NULL)
        return NULL;
    
 	//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);
    
    return root;
}

(98验证二分搜索树) 给定一个二叉树，判断其是否是一个有效的二叉搜索树。

// 中序遍历一颗二分搜索树将得到一个有序数组
class Solution {
public:
    bool isValidBST(TreeNode* root) {

        vector<int> vec;
        inOrder(root, vec);
        for(int i = 1 ; i < vec.size() ; i ++)
            if(vec[i-1] >= vec[i])
                return false;
        return true;
    }

private:
    void inOrder(TreeNode* node, vector<int>& vec){

        if(node == NULL)
            return;

        inOrder(node->left, vec);
        vec.push_back(node->val);
        inOrder(node->right, vec);
    }
};

// 递归版
class Solution {
public:
    bool isValidBST(TreeNode* root) {

        return isValidBST(root, INT_MIN, INT_MAX);
    }

private:
    bool isValidBST(TreeNode* node, int min, int max){

        if(node == NULL)
            return true;

        if(node->val < min || node->val > max)
            return false;

        if(node->left != NULL && node->left->val >= node->val)
            return false;

        if(node->right != NULL && node->right->val <= node->val)
            return false;

        return isValidBST(node->left, min, node->val - 1) && isValidBST(node->right, node->val + 1, max);
    }
};

(450删除二分搜索树中的节点) 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

示例:

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

给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
    5
   / \
  4   6
 /     \
2       7

另一个正确答案是 [5,2,6,null,4,null,7]。

    5
   / \
  2   6
   \   \
    4   7

     class Solution {
     public:
         TreeNode* deleteNode(TreeNode* root, int key) {
     
             if(!root)
                 return NULL;
     
             if(key < root->val){
                 root->left = deleteNode(root->left, key);
                 return root;
             }
     
             if(key > root->val){
                 root->right = deleteNode(root->right, key);
                 return root;
             }
     
             if(!root->right) return root->left;
     
             if(!root->left) return root->right;
     
             TreeNode* p = root, *minnode = root->right;
             while(minnode->left){
                 p = minnode;
                 minnode = minnode->left;
             }
     
             root->val = minnode->val;
             root->right = deleteMinNode(root->right);
             return root;
         }
     
     private:
         TreeNode* deleteMinNode(TreeNode* root){
     
             if(!root->left) return root->right;
             root->left = deleteMinNode(root->left);
             return root;
         }
     };

(108将有序数组转换为二分搜索树) 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

示例:

给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

     class Solution {
     public:
         TreeNode* sortedArrayToBST(vector<int>& nums) {
     
             if(nums.size() == 0)
                 return NULL;
             return buildTree(nums, 0, nums.size() - 1);
         }
     
     private:
         TreeNode* buildTree(const vector<int>& nums, int l, int r){
     
             if(l > r) return NULL;
             if(l == r) return new TreeNode(nums[l]);
     
             int mid = (l + r) / 2;
             TreeNode* root = new TreeNode(nums[mid]);
             root->left = buildTree(nums, l, mid - 1);
             root->right = buildTree(nums, mid + 1, r);
             return root;
         }
     };

(230二分搜索树中第k小的元素) 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

示例:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 1

     // 中序遍历
     class Solution {
     
     private:
         int index;
     
     public:
         int kthSmallest(TreeNode* root, int k) {
             index = 0;
             return kthSmallestNode(root, k)->val;
         }
     
     private:
         TreeNode* kthSmallestNode(TreeNode* node, int k){
     
             if(node == NULL)
                 return NULL;
     
             TreeNode* res = kthSmallestNode(node->left, k);
             if(res) return res;
     
             index ++;
             if(index == k)
                 return node;
     
             return kthSmallestNode(node->right, k);
         }
     };

(236二叉树中的最近公共祖先) 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

     // 找到两条路径
     class Solution {
     public:
         TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
     
             vector<TreeNode*> path1;
             dfs(root, p, path1);
     
             vector<TreeNode*> path2;
             dfs(root, q, path2);
     
             TreeNode* res;
             for(int i = 0; i < path1.size() && i < path2.size(); i ++)
                 if(path1[i] == path2[i]) res = path1[i];
                 else break;
             return res;
         }
     
     private:
         bool dfs(TreeNode* node, TreeNode* target, vector<TreeNode*>& path){
     
             if(!node) return false;
     
             path.push_back(node);
             if(node == target) return true;
     
             if(dfs(node->left, target, path)) return true;
             if(dfs(node->right, target, path)) return true;
     
             path.pop_back();
             return false;
         }
     };
     // 递归版
     class Solution {
     public:
         // 在root中寻找p和q
         // 如果p和q都在root所在的二叉树中, 则返回LCA
         // 如果p和q只有一个在root所在的二叉树中, 则返回p或者q
         // 如果p和q均不在root所在的二叉树中, 则返回NULL
         TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
     
             if(root == NULL)
                 return root;
     
             if(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;
     
             if(left != NULL)
                 return left;
     
             if(right != NULL)
                 return right;
     
             return NULL;
         }
     };

内容总结

以上是互联网集市为您收集整理的算法经典面试题（5）——二叉树全部内容，希望文章能够帮你解决算法经典面试题（5）——二叉树所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/606395.html

来源：【匿名】

【上一篇】数据结构与算法—栈详解(看完面试考试再也不怕了)【下一篇】色色整理的PHP面试题集锦

更多 ►

【算法经典面试题（5）——二叉树】教程文章相关的互联网学习教程文章

1.position的值， relative和absolute分别是相对于谁进行定位的？absolute :生成绝对定位的元素，相对于最近一级的定位不是 static 的父元素来进行定位。fixed （老IE不支持）生成绝对定位的元素，相对于浏览器窗口进行定位。relative 生成相对定位的元素，相对于其在普通流中的位置进行定位。static 默认值。没有定位，元素出现在正常的流中2.如何解决跨域问题 JSONP：原理是：动态插入script标签，通过script标签引入一个js文件...

常见面试题--爬楼梯【代码】

有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶，问小孩有多少种走法可以上去，类似的问题很多。典型的动态规划问题设到达第 i 阶台阶有f(i)种走法我们可以轻易的发现当阶梯数 n = 1 时，f(1) = 1;　　　　　　　　　　　　　　n = 2时，f(2) = 2;　　　　　　　　　　　　　　n = 3时，f(n) = 4;当n>=4时，假设小孩当前处于第 i 阶，那么他的前一步有3种可能：　　1.在 i-1 阶上1阶到达第 i 阶　　2.在 i-2 阶...

LeetCode面试题 08.12. 八皇后---回溯算法解决N皇后问题(C++实现）【代码】

N皇后问题源于著名的八皇后问题：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法！将8x8扩展为NxN即为N皇后问题，要解决此问题，最简单的方法就是暴力枚举，此时的时间复杂度为N^2，回溯算法与简单暴力枚举类似，不同点在于当判定某种状态不符合答案时，便不再继续枚举此状态的后续状态，而是回溯到该状态之前，继续遍历其他的可能值。 1 #include <ios...

Java基础面试题集（二）

Java程序员面试题集（1-50）一、Java基础部分1、面向对象的特征有哪些方面?答：面向对象的特征主要有以下几个方面：1)抽象：抽象是将一类对象的共同特征总结出来构造类的过程，包括数据抽象和行为抽象两方面。抽象只关注对象有哪些属性和行为，并不关注这些行为的细节是什么。2)继承：继承是从已有类得到继承信息创建新类的过程。提供继承信息的类被称为父类（超类、基类）；得到继承信息的类被称为子类（派生类）。3)封装：通常认...

面试题中问到 aop di ioc 怎么回答

ioc 就是我们需要一个对象以前我们是去 new 现在我们是直接向 spring 要我们需要的那个对象。aop 就是在不修改源代码的基础上添加新业务，比如日志性能检测di 就是一个对象a 需要去访问数据库以前我们是自己编写代码去创建一个connction对象来连接对象，现在我们只需要用@autowrite来获取connection对象，在系统运行时，spring会在合适的时候去创建这个对象，对象a不必关心connection是怎么创建的，何时创建的，这就完成了...

【转】典型的JavaScript面试题【代码】

问题1: 作用域（Scope）1 (function() { 2 "use strict"; 3var a = b = 5; 4})(); 5 console.log(b); 控制台（console）会打印出什么？答案：上述代码会打印出5。这个问题的陷阱就是，在立即执行函数表达式（IIFE）中，有两个赋值，但是其中变量a使用关键词var来声明。这就意味着a是这个函数的局部变量。与此相反，b被分配给了全局作用域（译注：也就是全局变量）。这个问题另一个陷阱就是，在函数中没有使用”严格模式” (‘use...

HashMap源码与相关面试题【代码】【图】

一、哈希表哈希表是一种可以快速定位得数据结构。哈希表可以做到平均查找、插入、删除时间是O(1)，当然这是指不发生Hash碰撞得情况。而哈希表最大得缺陷就是哈希值得碰撞(collision)。Hash碰撞：就是指hash桶有多个元素了。常见解决哈希碰撞得方法就是在hash桶后面加个链表这里就引入第一个问题：为什么Map的底层设计要采用哈希表的这种数据结构？HashMap设计时，要求其key不能重复。所以每次往HashMap设置值时，需要对HashMap现在...

Java面试题总结之OOA/D,UML,和XML【代码】【图】

全文字数： 2732阅读时间：大约9 分钟1、UML 是什么？常用的几种UML图？统一建模语言（Unified Modeling Language，UML）又称标准建模语言；常用图包括：用例图,静态图(包括类图、对象图和包图),行为图,交互图(顺序图, 协作图),实现图。2、编程题: 写一个Singleton(单例模式) 出来。 Singleton 模式主要作用是保证在Java 应用程序中，一个类Class 只有一个实例存在。举例：定义一个类，它的构造函数为private 的，它有一...

面试题1：二维数组中查找【代码】【图】

本题出自《剑指offer 名企面试官精讲典型编程题》面试题3。题目3：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列按照从上到下递增的顺序排序。请完成一个函数，输入一个这样的二维数组和整数，判断数组中是否含有该整数。例如下面的二维数组就是每行每列递增排序。如果在数组中查询7，则返回true；如果查找数字14，由于数组中不包含14，则返回false。解决方法分析：首先我们选取二维...

.net常见的面试题【图】

1，asp.net中的页生命周期　　答：msdn官网已给出标准答案，这里简述一下：页要经历下表概述的8个阶段。除了页生命周期阶段以外，在请求前后还存在应用程序阶段，但是这些阶段并不特定于页。　　而这8个阶段有：页请求，开始，页初始化，加载，验证，回发事件处理，呈现，卸载阶段。　　在页请求阶段，asp.net将确定是否需要分析和编译活着使用缓存进行响应；开始阶段确定是新请求还是回发请求；页初始化阶段设置控件uniqueID属性并...

java基础面试题

1.什么是Java虚拟机?为什么Java被称作是“平台无关的编程语言”?Java虚拟机是一个可以执行Java字节码的虚拟机进程。Java源文件被编译成能被Java虚拟机执行的字节码文件。Java被设计成允许应用程序可以运行在任意的平台，而不需要程序员为每一个平台单独重写或者是重新编译。Java虚拟机让这个变为可能，因为它知道底层硬件平台的指令长度和其他特性。 2.JDK和JRE的区别是什么?Java运行时环境(JRE)是将要执行Java程序的Java虚拟机。它...

ML面试题网站

一、最全http://www.epx365.cn/jyzn/201839501.html二、七月https://blog.csdn.net/movie14/article/details/79344131原文：https://www.cnblogs.com/always-fight/p/9438647.html

关于C++的面试题

一、谈一谈static 这个问题不算太难，但是要完整的把static的作用说完还是有一定难度的。A、首先解释static在C语言中的作用，这些作用在C++中被完全继承了。（1）所有使用static修饰过的变量如果未被显式初始化，则被存储在bss段，BSS段在二进制程序中是没有实际存储的，只有在程序运行时才会为BSS段分配内存同时进行默认初始化，在C语言中也就是赋值为0 。如果显示初始化了，那么就存储在data段。而不管是bss段还是data段，...

ajax面试题

1.用post方式异步向服务器端提交数据时,需要在发送请求前设置什么?提交的数据放在什么位置?答案:xhr.setRequestHeader("Content-Type",application/x-www-form-urlencoded);数据放在send()括号中. 2.什么是异步数据加载?答案:浏览器在向服务器发送请求的时候,不耽误用户在网页上做其他操作,可以同时开启多个任务,并且可以以无刷新的效果来更改页面中的局部内容. 3.异步请求数据的步骤分为哪几步?答案:创建异步对象,绑定监听对象,创...

九章算法面试题28 链表找环

九章算法官网-原文网址http://www.jiuzhang.com/problem/28/题目初阶：给一个单链表，判断这个单链表是否存在环，如1->2->3->4->2是一个存在环的链表。要求使用O(1)的额外空间。进阶：求出环的入口。同样要求O(1)的额外空间。解答初阶：用两根指针，从链表头出发，一根慢指针每次走一步，另外一根快指针每次走两步。直到他们相遇（有环）或者快指针走到NULL（无环）。进阶：相遇之后，将一根指针挪到链表头，两根指针每次都移动一步...

面试 - 最热教程

10个最常见的HTML5面试题及答案 Netty面试题（2020）java各公司面试记录 Android 开发面试题集合整理（内含答案...4轮字节面试后杳无音信，自己是在了备胎...Java面试题分享 php面试题五之nginx如何调用php和php-f...安卓rxjava使用，Android性能优化面试题...Java 面试——Zookeeper android逆向！Android开发岗还不会这些...

首页 / 面试 / 算法经典面试题（5）——二叉树

算法经典面试题（5）——二叉树

内容导读

内容图文

二叉树

内容总结

内容备注

内容手机端

【算法经典面试题（5）——二叉树】教程文章相关的互联网学习教程文章

添优--史上超级全面的前端面试题大集合【图】

常见面试题--爬楼梯【代码】

LeetCode面试题 08.12. 八皇后---回溯算法解决N皇后问题(C++实现）【代码】

Java基础面试题集（二）

面试题中问到 aop di ioc 怎么回答

【转】典型的JavaScript面试题【代码】

HashMap源码与相关面试题【代码】【图】

Java面试题总结之OOA/D,UML,和XML【代码】【图】

面试题1：二维数组中查找【代码】【图】

.net常见的面试题【图】

java基础面试题

ML面试题网站

关于C++的面试题

ajax面试题

九章算法面试题28 链表找环

算法 - 相关标签

面试 - 最新教程

面试 - 最热教程