Leetcode-Question-563: Binary Tree Tilt

原文链接:

https://leetcode.com/problems/binary-tree-tilt/

解析:

 

Leetcode-Question-94: Binary Tree Inorder Traversal

原文链接:
https://leetcode.com/problems/binary-tree-inorder-traversal/

题目描述:
94. Binary Tree Inorder Traversal My Submissions Question
Total Accepted: 103676 Total Submissions: 271373 Difficulty: Medium
Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

解答:

参考https://leetcode.com/discuss/36713/solutions-iterative-recursive-traversal-different-solutions

法一:我的老笨办法O(n) Time, O(n) Space (就是把前序的稍微一改……)

法二)更优雅一点的非递归遍历O(n) Time, O(n) Space.

法二 2017.09.18

法三)大杀器Morris 遍历 O(n) Time, O(1) Space.

Updated 2017.10.30 破坏原树结构的Morris遍历

Step 1: Initialize current as root

Step 2: While current is not NULL,

If current does not have left child

a. Add current’s value

b. Go to the right, i.e., current = current.right

Else

a. In current’s left subtree, make current the right child of the rightmost node

b. Go to this left child, i.e., current = current.left

 

Leetcode-Question-110: Balanced Binary Tree

原文链接:
https://leetcode.com/problems/balanced-binary-tree/

题目描述:

  1. Balanced Binary Tree
    Difficulty: Easy

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.

解析:

  • 自顶向下方法,时间复杂度为O(n^2)

 

  • 自底向上方法,DFS,时间复杂度为O(n).