Tag Archives:

LeetCode Find Largest Value in Each Tree Row

LeetCode Find Largest Value in Each Tree Row You need to find the largest value in each row of a binary tree. Example:

Input:
          1
         / \
        3   2
       / \   \
      5   3   9
Output: [1, 3, 9]

给定一棵二叉树,找出每层的最大值。 简单题,直接BFS,在每一层找最大值。代码如下: [cpp] class Solution { public: vector<int> largestValues(TreeNode* root) { vector<int> ans; if (!root)return ans; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int largest = INT_MIN, n = q.size(); while (n–) { TreeNode* front = q.front(); q.pop(); largest = max(largest, front->val); if (front->left)q.push(front->left); if (front->right)q.push(front->right); } ans.push_back(largest); } return ans; } }; [/cpp] 本代码提交AC,用时13MS。]]>

LeetCode Find Bottom Left Tree Value

LeetCode Find Bottom Left Tree Value Given a binary tree, find the leftmost value in the last row of the tree. Example 1:

Input:
    2
   / \
  1   3
Output:
1
Example 2:
Input:
        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7
Output:
7
Note: You may assume the tree (i.e., the given root node) is not NULL.
找出一棵二叉树最后一行的最左边元素。 简单题,直接BFS,每层保存队列第一个元素,BFS结束之后,就能得到最后一行的第一个元素。 代码如下: [cpp] class Solution { public: int findBottomLeftValue(TreeNode* root) { queue<TreeNode*> q; q.push(root); int ans = 0; while (!q.empty()) { int n = q.size(); ans = q.front()->val; while (n–) { TreeNode* front = q.front(); q.pop(); if (front->left)q.push(front->left); if (front->right)q.push(front->right); } } return ans; } }; [/cpp] 本代码提交AC,用时12MS。]]>

LeetCode Diameter of Binary Tree

543. Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

          1
         / \
        2   3
       / \     
      4   5    

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.


本题要求一棵树的直径,树的直径的定义是树中任意两点间的最长距离。
任意两点间的最长路径有如下三种选择:

  1. 经过根节点的最长路径
  2. 在左子树中不经过根节点的最长路径
  3. 在右子树中不经过根节点的最长路径

其中第1种情况比较好处理,必须经过根节点,又必须是最长路径,则路径长度肯定是左右子树的最大高度之和+1(根节点)。第2、3种情况就更好处理了,就是以左右孩子为根递归计算最长路径。
代码如下:

class Solution {
private:
    int getHeight(TreeNode* root)
    {
        if (!root)
            return 0;
        int lh = getHeight(root->left);
        int rh = getHeight(root->right);
        return 1 + max(lh, rh);
    }

public:
    int diameterOfBinaryTree(TreeNode* root)
    {
        if (!root)
            return 0;
        //int ans = 1 + getHeight(root->left) + getHeight(root->right); // 节点数
        int ans = getHeight(root->left) + getHeight(root->right); // 路径数
        ans = max(ans, diameterOfBinaryTree(root->left));
        ans = max(ans, diameterOfBinaryTree(root->right));
        return ans;
    }
};

本代码提交AC,用时22MS。

参考:http://www.geeksforgeeks.org/diameter-of-a-binary-tree/,这篇博客的路径是指节点数,而本题的路径是指边数,所以第12行不能再加1了。

以上代码递归的过程是从根节点往孩子节点递归,这样计算高层节点的高度时,其实已经计算过低层节点的高度了,后面递归到低层节点时,会重复计算。所以代码还可以优化,比如可以不断递归到叶子节点再返回,这样高层节点的高度就可以直接用低层节点的高度加1计算得到,可以省不少时间。

二刷。在求解路径的同时可计算高度,而且先递归到叶子,然后不断从往上走,代码如下:

class Solution {
public:
	int DiameterAndHeight(TreeNode* root, int &height) {
		if (root == NULL || (root->left == NULL && root->right == NULL)) {
			height = 0;
			return 0;
		}
		int left_height = 0, right_height = 0;
		int left_diameter = DiameterAndHeight(root->left, left_height);
		int right_diameter = DiameterAndHeight(root->right, right_height);
		height = max(left_height, right_height) + 1;
		int left_edge = root->left == NULL ? 0 : 1, right_edge = root->right == NULL ? 0 : 1;
		return max(max(left_diameter, right_diameter), left_height + right_height + left_edge + right_edge);
	}
	int diameterOfBinaryTree(TreeNode* root) {
		int height = 0;
		return DiameterAndHeight(root, height);
	}
};

本代码提交AC,用时8MS,快了不少。

LeetCode Minimum Absolute Difference in BST

LeetCode Minimum Absolute Difference in BST Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes. Example:

Input:
   1
    \
     3
    /
   2
Output:
1
Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).
Note: There are at least two nodes in this BST.
求一棵二叉搜索树中任意两个节点数值之差的绝对值的最小值。 因为是BST,所以满足左子树<=根节点<=右子树。以根节点root为例,则最小的差可能有两个,一个是root减去左子树中的最大数,另一个是右子树中的最小数减去root,所以整体的最小值就是这两个最小值的最小值。 左子树中的最大数就是左子树中最右下端的叶子节点,右子树中的最小数就是右子树中最左下端的叶子节点。 然后递归的以左右孩子为根更新最小值。代码如下: [cpp] class Solution { public: int getMinimumDifference(TreeNode* root) { int l = INT_MIN, r = INT_MAX; int left_min = INT_MAX, right_min = INT_MAX; if (root->left) { TreeNode* left = root->left; while (left->right)left = left->right; left_min = min(root->val – left->val, getMinimumDifference(root->left)); } if (root->right) { TreeNode* right = root->right; while (right->left)right = right->left; right_min = min(right->val – root->val, getMinimumDifference(root->right)); } return min(left_min, right_min); } }; [/cpp] 本代码提交AC,用时19MS。 还有一种思路,因为是BST,所以其中序遍历的结果是升序的,得到有序数组之后,相邻两个数的差的最小值就是要求的结果。 实际上,我们可以不用完整求出其升序序列之后再计算差,只需要在每次中序遍历时,记住该节点的上一个节点,这样该节点的值减去上一节点的值就相当于有序数组中相邻两个数作差。 代码如下: [cpp] class Solution { private: long long m_nLast, m_nAns; void inorderTraverse(TreeNode* root) { if (!root)return; inorderTraverse(root->left); // 左 m_nAns = min(m_nAns, root->val – m_nLast); m_nLast = root->val; // 根 inorderTraverse(root->right); // 右 } public: Solution() { m_nLast = INT_MIN; m_nAns = INT_MAX; } int getMinimumDifference(TreeNode* root) { inorderTraverse(root); return m_nAns; } }; [/cpp] 本代码提交AC,用时16MS。注意因为可能出现x-INT_MIN导致int溢出,所以两个成员变量定义为long long。 参考:http://bookshadow.com/weblog/2017/02/26/leetcode-minimum-absolute-difference-in-bst/]]>

LeetCode Path Sum III

LeetCode Path Sum III 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. Example:

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

问二叉树中有多少条路径和等于sum的路径,这里的路径不一定要起于根节点,也不一定要终于叶子结点,但是必须从从上往下(从父亲到孩子)。 我一开始的解法是,对每个节点,保留从其所有父亲节点到该节点的路径和,每个节点都统计到当前节点的路径和等于sum的路径数。 代码如下: [cpp] class Solution { private: void dfs(TreeNode* root, vector<int> all, int target, int& ans) { vector<int> newAll = { root->val }; for (int i = 0; i < all.size(); ++i)newAll.push_back(root->val + all[i]); for (int i = 0; i < newAll.size(); ++i) { if (newAll[i] == target)++ans; } if (root->left)dfs(root->left, newAll, target, ans); if (root->right)dfs(root->right, newAll, target, ans); } public: int pathSum(TreeNode* root, int sum) { if (root == NULL)return 0; int ans = 0; dfs(root, {}, sum, ans); return ans; } }; [/cpp] 本代码提交AC,用时62MS。这种解法需要保存所有的路径和,且有vector的复制,效率较低。 我这种解法是以每个节点作为终点统计一下路径和,网上有另一种解法,以每个节点作为开始节点,统计以这个点开始的所有路径和是否等于sum,然后递归的在其子树进行统计。 对于每个节点,走到其孩子节点时,对应的sum需要更新。代码如下: [cpp] class Solution { private: int dfs(TreeNode* root, int sum) { if (root == NULL)return 0; int ans = 0; if (root->val == sum)++ans; ans += dfs(root->left, sum – root->val); ans += dfs(root->right, sum – root->val); return ans; } public: int pathSum(TreeNode* root, int sum) { if (root == NULL)return 0; return dfs(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum); } }; [/cpp] 本代码提交AC,用时32MS,效率更高。]]>

LeetCode Delete Node in a BST

LeetCode Delete Node in a BST 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:

  1. Search for a node to remove.
  2. If the node is found, delete the node.
Note: Time complexity should be O(height of tree). Example:
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

从二叉搜索树中删除一个节点,并返回一个新的二叉搜索树;如果该节点不存在,则返回原二叉搜索树。 因为是BST,所以很容易找到等于value的节点,问题的关键是怎样删除这个节点,并且保持二叉搜索树的特性:左孩子<根节点<右孩子。 如果要删除的节点的左子树为空,则删除该节点,返回该节点的右子树即可;类似的,如果要删除的节点的右子树为空,则删除该节点,返回该节点的左子树。 难点就是当该节点的左子树和右子树都不为空时,该怎么处理。如下图,假设我们找到了root的值等于key,则需要删除root节点,并调整其子树使满足BST的性质。
       root
      /    \
   left  right
  /   \  /   \
 x    l r     y
具体有两种方案,题目中也举了例子,即可以把left放到root的位置,或者把right放到root的位置。 现在假设要把left放到root的位置,则需要处理left的右子树l。l肯定要被切下来,又l比left大,所以l应该接在right子树,具体位置是接在right子树的最小节点上,即right的最左下端的叶子节点r。也就是变成下面这样:
    left            right
    /  \            /   \
   x               r     y
                  /
                 l 
最后把right子树接在left右子树即可:
            left
            /  \
           x    right
                /   \
               r     y
              /
             l  
知道了调整的思路,代码就好写了: [cpp] class Solution { private: TreeNode* justify(TreeNode *root) { if (root->left == NULL || root->right == NULL)return root->left == NULL ? root->right : root->left; TreeNode *left = root->left, *right = root->right; TreeNode *l = left->right, *r = right; while (r->left) r = r->left; r->left = l; left->right = right; return left; } public: TreeNode* deleteNode(TreeNode* root, int key) { TreeNode *dummy = new TreeNode(-1), *pre = dummy, *child = root; dummy->right = root; while (child != NULL && child->val != key) { pre = child; if (key < child->val) child = child->left; else child = child->right; } if (child == NULL)return dummy->right; if (pre->left == child)pre->left = justify(child); else pre->right = justify(child); return dummy->right; } }; [/cpp] 本代码提交AC,用时33MS。 如果要把right放到root的位置,思路是类似的,需要把right的左子树切下来接到left最右下端的叶子节点上。 参考:https://segmentfault.com/a/1190000005032508]]>

LeetCode Construct Binary Tree from Inorder and Postorder Traversal

106. Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

本题要根据树的中序和后序遍历结果,重构出树的结构。 有了之前LeetCode Construct Binary Tree from Preorder and Inorder Traversal根据前序和中序重构树的算法,这一题就是照猫画虎了。因为后序遍历是最后一个数为根节点,和前序遍历其实没本质差别。找准inorder和postorder下标的起止位置就可以开始写代码了:

class Solution {
private:
    TreeNode* dfs(vector<int>& inorder, vector<int>& postorder, int inL, int inR, int postL, int postR, unordered_map<int, int>& hash)
    {
        if (inL > inR || postL > postR)
            return NULL;
        TreeNode* root = new TreeNode(postorder[postR]);
        int idx = hash[root->val];
        root->right = dfs(inorder, postorder, inL + 1, inR, postR – (inR – idx), postR – 1, hash);
        root->left = dfs(inorder, postorder, inL, idx – 1, postL, postR – (inR – idx) – 1, hash);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
    {
        if (inorder.size() == 0)
            return NULL;
        unordered_map<int, int> hash;
        for (int i = 0; i < inorder.size(); ++i) {
            hash[inorder[i]] = i;
        }
        return dfs(inorder, postorder, 0, inorder.size() – 1, 0, postorder.size() – 1, hash);
    }
};

本代码提交AC,用时16MS。

LeetCode Construct Binary Tree from Preorder and Inorder Traversal

105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

根据树的先序遍历和中序遍历结果,重构这棵树。 其实大学的时候就有这样的作业,如果在纸上做,还是很简单的,但要实现成代码,稍微有点难理清这里的关系。 我们先来看一个纸上的解题过程,假设有下面这样一棵树:

        3
     /     \
    9       20
  /  \     /   \
 1    2  15    17
  • 先序遍历结果为:3, 9, 1, 2, 20, 15, 17
  • 中序遍历结果为:1, 9, 2, 3, 15, 20, 17

首先我们可以根据先序遍历结果找到根节点3,然后在中序遍历中看看3所处的位置,那么3左边的就是左孩子节点,右边的就是右孩子节点。我们在中序遍历中看看3左边有3个节点,说明3的左子树共有3个节点,同理右子树有3个节点。所以我们在先序遍历中也能知道3后面的3个节点是左子树,再后面3个节点是右子树,这样就把两个遍历结果分成了两部分:

  • 先序遍历结果为:3, 9, 1, 2, 20, 15, 17
  • 中序遍历结果为:1, 9, 2, 3, 15, 20, 17

在红色部分递归就是3的左子树,在蓝色部分递归就是3的右子树。 纸上解题好说,但是代码实现,我开始还把自己搞糊涂了,代码很复杂,后来参考了这位大神的博客,代码好简洁易懂,赞一个:

class Solution {
private:
    TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int preL, int preR, int inL, int inR, unordered_map<int, size_t>& hash)
    {
        if (preL > preR || inL > inR)
            return NULL;
        TreeNode* root = new TreeNode(preorder[preL]);
        size_t idx = hash[root->val];
        root->left = dfs(preorder, inorder, preL + 1, idx – inL + preL, inL, idx – 1, hash);
        root->right = dfs(preorder, inorder, idx – inL + preL + 1, preR, idx + 1, inR, hash);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    {
        if (preorder.size() == 0)
            return NULL;
        unordered_map<int, size_t> hash;
        for (size_t i = 0; i < inorder.size(); ++i) {
            hash[inorder[i]] = i;
        }
        return dfs(preorder, inorder, 0, preorder.size() – 1, 0, inorder.size() – 1, hash);
    }
};


本代码提交AC,用时16MS。
代码中有两点需要注意的,一是为了在中序遍历中快速找到根节点,提前对中序遍历结果hash了,因为题目中说了不会有重复元素;二是在dfs递归的时候,要算好下标的起止位置,一定不要弄错了,特别是preorder在左右子树中的起止位置。

LeetCode Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

本题还是树的层次遍历,但是稍微有点不一样,要求奇数层从左往右输出,偶数层从右往左输出。常规的层次遍历使用BFS实现,即队列,这里要求颠倒顺序,马上想到用堆栈。
维护一个left2right布尔变量,当tru时,把孩子从左往右压栈,这样下一层的输出顺序就是从右往左了;当为false时相反。这里我们还需要用到两个堆栈,分别保存当前层和下一层的结果。
talk is cheap, show you the code!

class Solution {
public:
    vector<vector<int> > zigzagLevelOrder(TreeNode* root)
    {
        vector<vector<int> > ans;
        if (!root)
            return ans;
        bool left2right = true;
        stack<TreeNode*> stk;
        stk.push(root);
        while (!stk.empty()) {
            stack<TreeNode*> stk2;
            vector<int> cand;
            size_t n = stk.size();
            for (size_t i = 0; i < n; ++i) {
                TreeNode* top = stk.top();
                stk.pop();
                if (!top)
                    continue;
                cand.push_back(top->val);
                if (left2right) {
                    stk2.push(top->left);
                    stk2.push(top->right);
                }
                else {
                    stk2.push(top->right);
                    stk2.push(top->left);
                }
            }
            left2right = !left2right;
            if (!cand.empty())
                ans.push_back(cand);
            stk = stk2;
        }
        return ans;
    }
};

本代码提交AC,用时6MS。

二刷。不使用两个栈,而使用一个双端队列也可以:

class Solution {
public:
	vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
		vector<vector<int>> ans;
		if (root == NULL)return ans;
		deque<TreeNode*> q;
		q.push_back(root);
		bool left2right = true;
		while (!q.empty()) {
			vector<int> cur;
			if (left2right) {
				int n = q.size();
				for (int i = 0; i < n; ++i) {
					cur.push_back(q[i]->val);
				}
				ans.push_back(cur);
				for (int i = n - 1; i >= 0; --i) {
					TreeNode* tn = q.back();
					q.pop_back();
					if (tn->right)q.push_front(tn->right);
					if (tn->left)q.push_front(tn->left);
				}
				left2right = false;
			}
			else {
				int n = q.size();
				for (int i = n - 1; i >= 0; --i) {
					cur.push_back(q[i]->val);
				}
				ans.push_back(cur);
				for (int i = 0; i < n; ++i) {
					TreeNode* tn = q.front();
					q.pop_front();
					if (tn->left)q.push_back(tn->left);
					if (tn->right)q.push_back(tn->right);
				}
				left2right = true;
			}
		}
		return ans;
	}
};

本代码提交AC,用时4MS。

LeetCode Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Example:

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // return 3
iterator.next();    // return 7
iterator.hasNext(); // return true
iterator.next();    // return 9
iterator.hasNext(); // return true
iterator.next();    // return 15
iterator.hasNext(); // return true
iterator.next();    // return 20
iterator.hasNext(); // return false

Note:

  • next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
  • You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.

本题要求设计一个二叉搜索树的迭代器,迭代的输出当前树中最小值,并且要求next和hasNext是O(1)时间复杂度和O(h)空间复杂度,h为树的高度。 因为二叉搜索树的中序遍历是递增有序的序列,所以如果没有O(h)空间复杂度限制,则可以提前保存中序遍历结果,然后实现对数组的迭代器。但是这样的空间复杂度就是O(sizeof(tree)),不符合题意。 立马想到树的中序遍历的非递归实现,我们可以借助一个堆栈,先只把树的根和最左边的数压栈,这样栈顶元素就是树的最下角元素,也就是最小值。每调用一次next,返回当前栈顶元素,同时把栈顶元素的右孩子及右孩子的所有最左边的节点压栈。hasNext就好办,直接返回堆栈是否为空。 这样堆栈中最多会保存树高个数的节点,所以是O(h)的空间复杂度。完整代码如下:

class BSTIterator {
private:
    stack<TreeNode*> tree;
    void putAllLeft(TreeNode* root, stack<TreeNode*>& tree)
    {
        while (root != NULL) {
            tree.push(root);
            root = root->left;
        }
    }
public:
    BSTIterator(TreeNode* root) { putAllLeft(root, tree); } /** @return whether we have a next smallest number */
    bool hasNext() { return !tree.empty(); } /** @return the next smallest number */
    int next()
    {
        TreeNode* top = tree.top();
        tree.pop();
        putAllLeft(top->right, tree);
        return top->val;
    }
};

本代码提交AC,用时19MS。