ツリーノート

ツリーの天然再帰構造
ツリー再帰検索要素ツリー再帰解放空間復習ツリー関連のすべての操作
104. Maximum Depth of Binary Tree

struct TreeNode {
    int            val;
    TreeNode*    left;
    TreeNode*    right;
    TreeNode(int x): val(x), left(NULL),right(NULL) {}
};

// DFS 
int maxDepth(TreeNode *root)
{
    if (NULL == root)
        return 0;
    int l = maxDepth(root->left);
    int r = maxDepth(root->right);

    return l > r ? l + 1:r+1;
    // 
    //return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

// BFS ， 
int maxDepth(TreeNode *root)
{
    if (NULL == root)
        return 0;
    queue  que;
    int nCount = 1;
    int nDepth = 0;//  

    que.push(root);
    while(!que.empty()) {
        TreeNode *pTemp = que.front();
        que.pop();
        nCount --;

        if (pTemp->left)
            que.push(pTemp->left);
        if (pTemp->right)
            que.push(pTemp->right);

        if (nCount == 0) {
            nDepth ++;
            nCount = que.size();
        }
    }
    return nDepth;
}

111. Minimum Depth of Binary Tree

struct TreeNode {
    int            val;
    TreeNode    *left;
    TreeNode    *right;
    TreeNode(int x): val(x),left(NULL), right(NULL) {}
};

int minDepth(TreeNode *root) 
{
    if (NULL == root)
        return 0;
    int l = minDepth(root->left);
    int r = minDepth(root->right);
    if (!l)
        return r+1;
    if (!r)
        return l+1;
    return (l1:r+1;
}

226. Invert Binary Tree
100. Same Tree
101. Symmetric Tree
222. Count Complete Tree Nodes
110. Balanced Binary Tree
再帰的終了条件に注意
112. Path Sum
404. Sum of Left Leaves
257. Binary Tree Paths
113. Path Sum II
129. Sum Root to Leaf Numbers
より複雑な再帰論理
437. Path Sum III
二分探索ツリーの問題復習二分探索ツリーの基本操作:挿入、探索、削除、最大値、最小値、前駆、後続、上界、下界、rank、K番目大、K番目小要素
赤い黒い木は少し理解します
235. Lowest Common Ancestor of a Binary Search Tree
98. Validate Binary Search Tree
450. Delete Node in a BST
108. Convert Sorted Array to Binary Search Tree
230. Kth Smallest Element in a BST
236. Lowest Common Ancestor of a Binary Tree