数算再回顾（三）二叉树常见算法

前言

数（据结构）算（法）再回顾，加深记忆抗遗忘。

基于遍历的简单问题

var isSameTree = function (p, q) {
  // validate structure
  if (!p && !q) return true;
  if ((!p && q) || (p && !q)) return false;
  // p and q are both non-null, then validate value
  if (p.val === q.val) {
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
  }

  return false;
};

对称二叉树解法一：修改isSameTree逻辑，将同侧分支判断改为对称侧分支判断。

var isSymmetricHelper = function (p, q) {
  if (!p && !q) {
    return true;
  } else if (!p || !q) {
    return false;
  } else if (p.val !== q.val) {
    return false;
  } else {
    return isSameTree(p.left, q.right) && isSameTree(p.right, q.left);
  }
};
var isSymmetric = function (root) {
  if (!root) return true;
  return isSymmetricHelper(root.left, root.right);
};

对称二叉树解法二：层序遍历，判断每层是否对称。

var isSymmetric = function (root) {
  const queue = [root];

  while (root && queue.length) {
    let len = queue.length;
    const layer = [];
    while (len) {
      const node = queue.pop();
      // tip: To insert a value even if node equal to null for keeping nodes' order
      layer.push(node && node.val);
      if (node) {
        queue.unshift(node.left);
        queue.unshift(node.right);
      }
      len--;
    }
    for (let i = 0; i < Math.floor(layer.length / 2); i++) {
      if (layer[i] !== layer[layer.length - i - 1]) return false;
    }
  }

  return true;
};

对称二叉树解法三：先或中序遍历时压入左、右两个节点，每次 pop 两个节点，判断两节点是否值等。

var isSymmetric = function (root) {
  const stack = [];
  let p = (q = root);

  while (p || q || stack.length) {
    while (p || q) {
      stack.push(p, q);
      p = p?.left;
      q = q?.right;
    }

    const nodeQ = stack.pop();
    const nodeP = stack.pop();
    if (!nodeQ && !nodeP) {
      continue;
    } else if (!nodeQ || !nodeP) {
      return false;
    } else if (nodeQ.val !== nodeP.val) {
      return false;
    }
    q = nodeQ.left;
    p = nodeP.right;
  }

  return true;
};

// 翻转二叉树
var invertTree = function (root) {
  if (!root) return root;

  const temp = root.left;
  root.left = root.right;
  root.right = temp;

  invertTree(root.left);
  invertTree(root.right);

  return root;
};
// 后序遍历迭代法翻转二叉树
var invertTree = function (root) {
  const stack = [];
  let prev = null;
  let p = root;

  while (p || stack.length) {
    while (p) {
      stack.push(p);
      p = p.left;
    }

    const node = stack.pop();
    if (!node.right || node.right === prev) {
      const temp = node.left;
      node.left = node.right;
      node.right = temp;
      prev = node;
    } else {
      stack.push(node);
      p = node.right;
    }
  }

  return root;
};

深度/高度问题

// 递归
var maxDepth = function (root) {
  if (!root) return 0;
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};

// 后序遍历迭代实现
var maxDepth = function (root) {
  const stack = [];
  let prev = null;
  let depth = 0;

  while (root || stack.length) {
    while (root) {
      stack.push(root);
      root = root.left;
    }

    const node = stack.pop();
    if (!node.right || node.right === prev) {
      depth = Math.max(depth, stack.length + 1);
      prev = node;
    } else {
      stack.push(node);
      root = node.right;
    }
  }

  return depth;
};

注意求最小深度时，递归写法应考虑如下 case：

左、右都空：忽略子树深度，直接返回 1；
左孩子存在，右孩子空：应当忽略右子树的深度，否则会有 root.right = null，此时右子树不是叶子节点，但却被 min 函数计算了；
左孩子空，右孩子存在：应当忽略左子树的深度，同理；
左、右都存在：计算左、右子树深度；

// 递归
var minDepth = function (root) {
  if (!root) return 0;

  if (!root.left && !root.right) return 1;

  const dl = root.left ? minDepth(root.left) : Infinity;
  const dr = root.right ? minDepth(root.right) : Infinity;

  return Math.min(dl, dr) + 1;
};
// 更优雅
var minDepth = function (root) {
  if (!root) return 0;

  if (!root.left && !root.right) return 1;

  const dl = minDepth(root.left);
  const dr = minDepth(root.right);

  if (!root.left || !root.right) return dl + dr + 1;

  return Math.min(dl, dr) + 1;
};

路径问题

112

根-叶路径和问题较为简单，因为指定路径端点为根、叶节点，一次后序遍历就可以解决：

每次递归将 target - 当前节点值，传递给下一层递归，直到最后一层递归，也就是访问到叶节点；此时判断叶节点值是否等于 target 即可；
注意每层递归需要归并下层递归的判断结果，也就是左或右子树路径和是否满足 target，最终在递归结束后得出总结果；
注意叶节点的值等于 target 才符合题意，必须通过左右子树不为空的条件，来限定只有叶节点执行值的比较，否则会出现特殊 case：某个分支节点的值恰好等于 target，导致 return true，

本身很简单，但容易忽视根到叶这一特殊 Case：

root=[1,2], target = 1，根节点的值虽然等于 1，但根节点有一个左孩子，所以根节点不算叶子节点，应当返回 false；
root=[1], target = 1，根节点同时也是叶子节点，且树的路径定义中，单个节点也可以构成路径，符合题意，应当返回 true；

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root) return false;

        bool result = hasPathSum(root->left, targetSum - root->val)
          || hasPathSum(root->right, targetSum - root->val);

        bool isLeaf = !root->left && !root->right;

        return result || isLeaf && root->val == targetSum;
    }
};

唯一需要注意的是，上述代码中的isLeaf很容易漏掉。

113

同样是根节点到叶节点的路径求和，只不过需要记录路径，迭代实现较为方便。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    int sum(vector<TreeNode*> arr) {
        int result = 0;
        for(int i = 0; i  < arr.size(); i++) {
            result += arr[i]->val;
        }
        return result;
    }
public:
    vector<int> nodeToInt(vector<TreeNode*> v) {
        vector<int> result;
        for(int i = 0; i < v.size(); i++) {
            result.push_back(v[i]->val);
        }
        return result;
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<TreeNode*> stack;
        vector<vector<int>> result;
        TreeNode* prev = nullptr;

        while(root || stack.size()) {
            while(root) {
                stack.push_back(root);
                root = root->left;
            }
            TreeNode* node = stack.back();

            if (node->right == nullptr || node->right == prev) {
                bool isLeafNode = node->left == nullptr && node->right == nullptr;
                if (isLeafNode && this->sum(stack) == targetSum) {
                    result.push_back(this->nodeToInt(stack));
                }
                stack.pop_back();
                prev = node;
            } else {
                root = node->right;
            }
        }

        return result;
    }
};

129

求根节点到叶节点数字之和，该问题的完整描述是——求出根-叶路径上，从根到叶的数字按顺序从左到右排列，所组成的新数字之和。递归思路是：

数字拼接：每层递归的值 + 上层递归拼接的数字 * 10；
结果归并：左右子树分别递归处理，结果相加；
结束条件：如果当前是叶子节点，数字拼接后直接返回结果；如果当前是空指针（度为 1 的节点会出现该情况），则返回 0，0 在求和中不影响结果；

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
using namespace std;
class Solution {
public:
    int sumNumbers(TreeNode* root, int prefix = 0) {
        if(root == nullptr) return 0;
        if(root->left == nullptr && root->right == nullptr) return prefix + root->val;

        int newPrefix = (prefix + root->val) * 10;

        return sumNumbers(root->left, newPrefix) + sumNumbers(root->right, newPrefix);
    }
};

257

同 113，换汤不换药，输出数组改为输出字符串；

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

using namespace std;
class Solution {
public:
    string nodesToString(vector<TreeNode*> v) {
        string result = "";
        for(int i = 0; i < v.size(); i++) {
            if(i == 0) {
                result = to_string(v[i]->val);
            } else {
                result = result + "->" + to_string(v[i]->val);
            }
        }

        return result;
    }
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<TreeNode*> stack;
        TreeNode* prev = nullptr;

        while(root != nullptr || stack.size() != 0) {
            while(root != nullptr) {
                stack.push_back(root);
                root = root->left;
            }
            TreeNode* node = stack.back();
            if(node->right == nullptr || node->right == prev) {
                if(node->left == nullptr && node->right == nullptr) {
                    result.push_back(this->nodesToString(stack));
                }
                stack.pop_back();
                prev = node;
            } else {
                root = node->right;
            }
        }

        return result;
    }
};

404

叶节点求和，也可以看作是叶节点单独组成的路径（长度为 1）之和，该题限定左叶节点，为了区分左右子树，可以引入一个 isLeft 变量用于标识左右；

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root, bool isLeft = false) {
        if (root == nullptr) return 0;
        if (root->left == nullptr && root->right == nullptr) return isLeft ? root -> val : 0;

        return sumOfLeftLeaves(root->left, true) + sumOfLeftLeaves(root->right);
    }
};

基于二叉树性质的问题

222. 完全二叉树的节点个数