TalkGo 算法之美第三期系列二

Kydaa · 2021 年1 月 3 日 14:15

系列二来啦！为期一周，本周难度较上周会有一定的提升。

周一：树的路径和计算

129. 求根到叶子节点数字之和

附加题：

124. 二叉树中的最大路径和

437. 路径总和 III

周三：二叉搜索树

1382. 将二叉搜索树变平衡

附加题：

面试题 04.05. 合法二叉搜索树

538. 把二叉搜索树转换为累加树

周五：巧用遍历

199. 二叉树的右视图

662. 二叉树最大宽度

kingeasternsun · 2021 年1 月 4 日 01:27

129

DFS


/**************一种dfs思路*********************/
func sumNumbers(root *TreeNode) int {

	if root == nil {
		return 0
	}

	totalSum := 0
	help(root, root.Val, &totalSum)
	return totalSum

}

// cur表示当前子节点，curNumber 表示从根节点到当前节点组成的数字，totalSum表示当前的数字之和
func help(cur *TreeNode, curNumber int, totalSum *int) {

	//到达叶子节点
	if cur.Left == nil && cur.Right == nil {
		*totalSum = *totalSum + curNumber
		return
	}

	if cur.Left != nil {
		help(cur.Left, curNumber*10+cur.Left.Val, totalSum)
	}

	if cur.Right != nil {
		help(cur.Right, curNumber*10+cur.Right.Val, totalSum)
	}
}

124



func maxPathSum(root *TreeNode) int {
	if root == nil {
		return 0
	}

	_, curSum := help(root)
	return curSum
}

func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}

// 返回当前节点对应子树上，以当前节点为起点的子路径的最大和， 以及当前节点为根节点的子树的上的最大路径和
func help(cur *TreeNode) (int, int) {

	if cur == nil {
		return math.MinInt32, math.MinInt32 //必须返回最小值
	}

	leftSingleSum, leftSum := help(cur.Left)
	rightSingleSum, rightSum := help(cur.Right)

	curSum := cur.Val + max(leftSingleSum, 0) + max(rightSingleSum, 0) //经过cur节点的最大路径和

	curSingleSum := cur.Val + max(max(leftSingleSum, rightSingleSum), 0) //以当前节点为起点的子路径的最大和

	return curSingleSum, max(max(leftSum, rightSum), curSum)

}

coolyeah · 2021 年1 月 4 日 07:34

129 求根到叶子节点数字之和

/*
回溯法
核心代码：做选择-递归-撤销选择
base case: 叶子节点累加数值
*/
class Solution1 {
   private:
    int sum = 0;
    void backstrace(TreeNode *root, string &str) {
        if (root->left == nullptr && root->right == nullptr) {
            sum += atoi(str.c_str());
            return;
        }
        if (root->left != nullptr) {
            str.push_back('0' + root->left->val);
            backstrace(root->left, str);
            str.pop_back();
        }
        if (root->right != nullptr) {
            str.push_back('0' + root->right->val);
            backstrace(root->right, str);
            str.pop_back();
        }
    }

   public:
    int sumNumbers(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }
        string str = "";
        str.push_back('0' + root->val);
        backstrace(root, str);
        return sum;
    }
};

// 社区的最佳答案，思路与上面一样，只是“和”可以更容易在递归中传递，在前序遍历中计算 sum
class Solution {
   public:
    int sumNumbers(TreeNode *root, int sum = 0) {
        if (root == nullptr) return 0;
        sum = 10 * sum + root->val;
        if (root->left == nullptr && root->right == nullptr) return sum;

        // 化整为零，把剩余的 sum 计算量传递下去
        return sumNumbers(root->left, sum) + sumNumbers(root->right, sum);
    }
};

124 二叉树中的最大路径和

class Solution {
   private:
    int maxsum = INT_MIN;

    // 了解题意，路径方向必须是向下的（只能从父节点到子节点），也就是路径是从整个树中截取两段交叉的链表
    // 节点中含有负数，使用 0 表示不将该节点加入路径
    // 函数是 寻找最大的一条链表的路径和
    int GetOneSideMaxSum(TreeNode *root) {
        if (root == nullptr) return 0;                      // null 节点不加入路径
        int left = max(0, GetOneSideMaxSum(root->left));    // 左子树的路径和少于 0 时不加入路径，大于 0 就加入路径
        int right = max(0, GetOneSideMaxSum(root->right));  // 右子树的路径和少于 0 时不加入路径，大于 0 就加入路径
        maxsum = max(maxsum, left + right + root->val);     // 以当前节点为顶点的两条链表的最大路径和，这里记录最大值
        return max(left, right) + root->val;                // 递归返回以当前节点为链表顶点的最大路径和，在递归上与父节点组成交叉的链表
    }

   public:
    int maxPathSum(TreeNode *root) {
        GetOneSideMaxSum(root);
        return maxsum;
    }
};

437 路径总和 III

/*
解法在于在二叉树中，寻找满足需求的 链表 的起点与终点
*/
class Solution {
   private:
    int result = 0;
    void findOneSideSum(TreeNode *root, int sum) {
        // null节点，前方无路，这里找不到终点了，返回
        if (root == nullptr) {
            return;
        }
        // 2、终点
        if (root->val == sum) {
            result++;
            // 这里不需要 return，或者后面还有路径和为 0 的链路
        }
        // 化整为零，把剩余的 sum 计算量传递下去
        findOneSideSum(root->left, sum - root->val);
        findOneSideSum(root->right, sum - root->val);
    }

   public:
    int pathSum(TreeNode *root, int sum) {
        if (root == nullptr) {
            return 0;
        }
        // 1、起点
        // 不一定从根节点开始，从每个子节点作为起点 计算 sum
        pathSum(root->left, sum);
        pathSum(root->right, sum);

        // 从某个节点作为起点
        findOneSideSum(root, sum);
        return result;
    }
};

从此萧郎是路人 · 2021 年1 月 4 日 12:21

129题

func sumNumbers(root *TreeNode) (ans int) {
	if root == nil {
		return
	}
	var dfs func(node *TreeNode, value int)
	dfs = func(node *TreeNode, value int) {
		curValue := value * 10 + node.Val
		if node.Left == nil && node.Right == nil {
			ans += curValue
			return
		}
		if node.Left != nil {
			dfs(node.Left, curValue)
		}
		if node.Right != nil {
			dfs(node.Right, curValue)
		}
	}
	dfs(root, 0)
	return
}

124题

func maxPathSum(root *TreeNode) int {
	if root == nil {
		return math.MinInt32
	}
	maxValue := math.MinInt32
	var maxPathToNode func(node *TreeNode) int
	maxPathToNode = func(node *interface{}) int {
		if node == nil {
			return math.MinInt32
		}
		leftMaxValue := max(0, maxPathToNode(node.Left))
		rightMaxValue := max(0, maxPathToNode(node.Right))
		curMaxPathSum := node.Val + leftMaxValue + rightMaxValue
		maxValue = max(maxValue, curMaxPathSum)
		return node.Val + max(leftMaxValue, rightMaxValue)
	}
	maxPathToNode(root)
	return maxValue
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

437题

func pathSum(root *TreeNode, sum int) (n int) {
	if root == nil {
		return
	}
	n = calPath(root, sum)
	n = n + pathSum(root.Left, sum) + pathSum(root.Right, sum)
	return
}

func calPath(node *TreeNode, sum int) (n int) {
	if node == nil {
		return
	}
	sum -= node.Val
	if sum == 0 {
		n = 1
	}
	n = n + calPath(node.Left, sum) + calPath(node.Right, sum)
	return
}

第1382题

func balanceBST(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	vals := inorderTraversal(root)
	return sortedArrayToBST(vals)
}

func inorderTraversal(root *TreeNode) (ans []int) {
	if root == nil {
		return
	}
	ans = append(ans, inorderTraversal(root.Left)...)
	ans = append(ans, root.Val)
	ans = append(ans, inorderTraversal(root.Right)...)
	return
}

func sortedArrayToBST(nums []int) *TreeNode {
	if len(nums) <= 0 {
		return nil
	}
	mid := len(nums) / 2
	root := &TreeNode{nums[mid], nil, nil}
	root.Left = sortedArrayToBST(nums[:mid])
	root.Right = sortedArrayToBST(nums[mid+1:])
	return root
}

面试题04.05

func isValidBST(root *TreeNode) bool {
	if root == nil {
		return true
	}
	order := inorderTraversal(root)
	for i := 0; i < len(order) - 1; i++ {
		if order[i] >= order[i + 1] {
			return false
		}
	}
	return true
}

func inorderTraversal(root *TreeNode) (ans []int) {
	if root == nil {
		return
	}
	ans = append(ans, inorderTraversal(root.Left)...)
	ans = append(ans, root.Val)
	ans = append(ans, inorderTraversal(root.Right)...)
	return
}

第538题

func convertBST(root *TreeNode) *TreeNode {
	sum := 0
	var helper func (node *TreeNode)
	helper = func(node *TreeNode) {
		if node == nil {
			return
		}
		helper(node.Right)
		node.Val += sum
		sum = node.Val
		helper(node.Left)
	}
	helper(root)
	return root
}

第199题

func rightSideView(root *TreeNode) (ans []int) {
	if root == nil {
		return
	}
	queue := []*TreeNode{}
	queue = append(queue, root)
	count := 1
	for len(queue) > 0 {
		var first *TreeNode
		for count > 0 {
			front := queue[0]
			queue = queue[1:]
			if first == nil {
				first = front
			}
			if front.Right != nil {
				queue = append(queue, front.Right)
			}
			if front.Left != nil {
				queue = append(queue, front.Left)
			}
            count--
		}
		ans = append(ans, first.Val)
		first = nil
        count = len(queue)
	}
	return
}

第662题

type RecordNode struct {
	*TreeNode
	pos int
}

func widthOfBinaryTree(root *TreeNode) int {
	if root == nil {
		return 0
	}
	queue := make([]*RecordNode, 0)
	queue = append(queue, &RecordNode{root, 1})
	count, left, ans := 0, 0, 1
	for len(queue) > 0 {
		count = len(queue)
		left = 0
		for count > 0 {
			front := queue[0]
            queue = queue[1:]
			if left == 0 {
				left = front.pos
			}
			ans = max(front.pos - left + 1, ans)
			if front.Left != nil {
				queue = append(queue, &RecordNode{front.Left, front.pos * 2})
			}
			if front.Right != nil {
				queue = append(queue, &RecordNode{front.Right, front.pos * 2 + 1})
			}
			count--
		}
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

席乐朋 · 2021 年1 月 5 日 09:23

129. 求根到叶子节点数字之和

方法一：深度优先搜索

func sumNumbers(root *TreeNode) int {
    return dfs(root, 0)
}
func dfs(root *TreeNode, prevSum int) int {
    if root == nil {
        return 0
    }
    sum := prevSum * 10 + root.Val
    if root.Left == nil && root.Right == nil {
        return sum
    }
    return dfs(root.Left, sum) + dfs(root.Right, sum)
}

时间复杂度：O(n)，其中 n 是二叉树的节点个数。对每个节点访问一次。

空间复杂度：O(n)，其中 n 是二叉树的节点个数。空间复杂度主要取决于递归调用的栈空间，递归栈的深度等于二叉树的高度，最坏情况下，二叉树的高度等于节点个数，空间复杂度为 O(n)。

124. 二叉树中的最大路径和

var res int
func maxPathSum(root *TreeNode) int {
    res = -1 << 63
    dfs(root)
    return res
}
func dfs(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := max(0, dfs(root.Left))
    right := max(0, dfs(root.Right))
    res = max(res, left + root.Val + right)
    return root.Val + max(left, right)
}
func max (x, y int) int {
    if x > y {
        return x
    }
    return y
}

437. 路径总和 III

var s int
var prefixSum map[int]int
func pathSum(root *TreeNode, sum int) int {
    s = sum
    prefixSum = map[int]int{}
    prefixSum[0] = 1
    return dfs(root, 0)
}
func dfs(root *TreeNode, cur int) int {
    if root == nil {
        return 0
    }
    cur += root.Val
    res := prefixSum[cur - s]
    prefixSum[cur] ++ 
    res += dfs(root.Left, cur) + dfs(root.Right, cur)
    prefixSum[cur] -- 
    return res
}

func pathSum(root *TreeNode, sum int) int {
    if root == nil {
        return 0
    }
    return dfs(root, sum) + pathSum(root.Left, sum) + pathSum(root.Right, sum)
}
func dfs(root *TreeNode, sum int) int {
    if root == nil {
        return 0
    }
    cnt := 0
    if root.Val == sum {
        cnt ++ 
    }
    cnt += dfs(root.Left, sum - root.Val)
    cnt += dfs(root.Right, sum - root.Val)
    return cnt
}

Icarus9913 · 2021 年1 月 5 日 14:49

129题，思路：可从root根向下遍历到每个叶子节点，每向下一次则当前值乘以10. 深度优先

int dfs(struct TreeNode* root, int pre){
    if(root==NULL){
        return 0;
    }
    int sum = pre * 10 + root->val;
    if(root->left==NULL && root->right==NULL){
        return sum;
    }
    return dfs(root->left,sum)+dfs(root->right,sum);
}

//主函数
int sumNumbers(struct TreeNode* root){
    return dfs(root,0);
}

Carl · 2021 年1 月 6 日 06:12

[面试题 04.05. 合法二叉搜索树 ]

func isValidBST(root *TreeNode) bool {

return helper(root, math.MinInt64, math.MaxInt64)

}

func helper(root *TreeNode, min, max int) bool {

if root == nil {

    return true

}

if root.Val >= max || root.Val <= min {

    return false

}

return helper(root.Left, min, root.Val) && helper(root.Right, root.Val, max)

}

coolyeah · 2021 年1 月 6 日 06:36

[1382] 将二叉搜索树变平衡

/*
思路：先对二叉搜索树进行 中序遍历出数组，再从数组构建出平衡二叉搜索树
*/
class Solution {
   private:
    void traversal(TreeNode* root, vector<TreeNode*>& arr) {
        if (root == nullptr) {
            return;
        }
        traversal(root->left, arr);
        arr.push_back(root);
        traversal(root->right, arr);
    }
    TreeNode* build(vector<TreeNode*>& arr, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        int mid = left + (right - left) / 2;
        TreeNode* node = arr[mid];
        node->left = build(arr, left, mid - 1);
        node->right = build(arr, mid + 1, right);
        return node;
    }

   public:
    TreeNode* balanceBST(TreeNode* root) {
        vector<TreeNode*> arr;
        traversal(root, arr);
        return build(arr, 0, arr.size() - 1);
    }
};

[98] 验证二叉搜索树

class Solution {
   private:
    TreeNode *pre = nullptr;  // 前驱，想像成 中序遍历的数组，遍历数组的前一个节点

   public:
    bool isValidBST(TreeNode *root) {
        if (root == nullptr) {
            return true;
        }
        bool left = isValidBST(root->left);
        // 第一次不为 nullptr，表示在中序遍历的第一个节点上了
        if (pre != nullptr && pre->val >= root->val) {
            return false;
        }
        // printf("%d ", root->val);  // 这里打印就是中序遍历的顺序输出

        // 之后第一个节点第一个递归返回后，会变成 pre
        pre = root;
        bool right = isValidBST(root->right);
        return left && right;
    }
};

[538] 把二叉搜索树转换为累加树

/*
根据题意，二叉搜索树的中序遍历是递增的，需要在中序遍历的序列上倒序遍历，累加数值
因此，解法是 右-中-左 的遍历中累加数值
*/
class Solution {
   private:
    int preVal = 0;

   public:
    TreeNode *convertBST(TreeNode *root) {
        if (root == nullptr) {
            return root;
        }
        convertBST(root->right);
        root->val += preVal;
        preVal = root->val;
        convertBST(root->left);
        return root;
    }
};

Carl · 2021 年1 月 9 日 01:33

199 题

func rightSideView(root *TreeNode) []int {
	result := new([]int)
	if root == nil {
		return *result
	}
	dfsVies(root, result, 0)
	return *result
}

func dfsVies(root *TreeNode, result *[]int, depth int) {
	if root == nil {
		return
	}
	if depth == len(*result) {
		*result = append(*result, root.Val)
	}
	depth++
	//注意当前顺序问题====》为解决退化成链表的形式
	dfsVies(root.Right, result, depth)

	dfsVies(root.Left, result, depth)
}

coolyeah · 2021 年1 月 9 日 10:08

[199] 二叉树的右视图

class Solution {
   public:
    vector<int> rightSideView(TreeNode *root) {
        vector<int> ret;
        if (root == nullptr) {
            return ret;
        }
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            int n = q.size();
            ret.push_back(q.back()->val);
            for (int i = 0; i < n; i++) {
                TreeNode *node = q.front();
                q.pop();
                if (node->left != nullptr) {
                    q.push(node->left);
                }
                if (node->right != nullptr) {
                    q.push(node->right);
                }
            }
        }
        return ret;
    }
};

[662] 二叉树最大宽度

/*
如题意，转化问题：求 二叉树转化成二叉堆 之后，每一层非null节点之间的最大长度
*/
class Solution {
   public:
    int widthOfBinaryTree(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }
        // leetcode 测试集有大树，使用 int 会溢出，所以使用 无符号长整形
        // size_t 是 long unsigned int
        typedef pair<TreeNode *, size_t> p_t;
        queue<p_t> q;
        q.push(p_t(root, 0));
        size_t ret = 0;
        while (!q.empty()) {
            int n = q.size();
            ret = max(ret, q.back().second - q.front().second + 1);
            for (int i = 0; i < n; i++) {
                p_t p = q.front();
                q.pop();
                TreeNode *node = p.first;
                size_t index = p.second;
                if (node->left != nullptr) {
                    q.push(p_t(node->left, index * 2));
                }
                if (node->right != nullptr) {
                    q.push(p_t(node->right, index * 2 + 1));
                }
            }
        }
        return (int)ret;
    }
};

kingeasternsun · 2021 年1 月 11 日 01:17

#124


func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}

func maxPathSum(root *TreeNode) int {
	if root == nil {
		return 0
	}

	res := math.MinInt32
	help(root, &res)
	return res

}

//res  目前所知的最大路径长度， 返回以cur为起点的单边最长路径
func help(cur *TreeNode, res *int) int {

	if cur == nil {
		return 0
	}

	left := help(cur.Left, res)
	if left < 0 {
		left = 0
	}
	right := help(cur.Right, res)
	if right < 0 {
		right = 0
	}

	//跟包含当前节点的最大路径长度进行比较，选取最大
	*res = max(*res, left+right+cur.Val)

	return max(left, right) + cur.Val

}

sunznx · 2021 年1 月 11 日 04:00